1) history.decode('utf-8') это уже строка, второй раз не надо.
2) Ошибка у вас при выводе на консоль, но в Pycharm консоль по умолчанию юникодная. В Windows тоже. Т.е., проверьте на всякий значение os.environ['PYTHONIOENCODING']. Прямо перед печатью.
