Повесть «Очарованный странник» (по Лескову — «рассказ»); была, по всей вероятности, задумана после летней поездки Н. С. Лескова в 1872 году по Ладожскому озеру, давшей ему материал для последней части «Очарованного странника». В первоначальном виде под названием «Черноземный Телемак» рассказ был послан в «Русский вестник», по-видимому в начале 1873 года. 8 мая 1873 года Н. А. Любимов сообщил Лескову отказ Каткова: «Михаил Никифорович прочел «Черноземного Телемака» и после колебаний пришел к заключению, что печатать эту вещь будет неудобно. Не говоря о некоторых эпизодах, как, например, о Филарете и св. Сергии, вся вещь кажется ему скорее сырым материалом для выделки фигур, теперь весьма туманных, чем выделанным описанием чего-либо действительности возможного и происходящего… Он советует вам подождать печатать эту вещь, самый мотив которой может, по его мнению, выделаться во что-либо хорошее» (см. А. Лесков. Жизнь Николая Лескова, стр. 296). В письме к Щебальскому («Шестидесятые годы», Стр. 327, письмо от 4 января 1873 г.), отвечая на его критические замечания об «Очарованном страннике», Лесков писал уже после публикации повести, имея в виду мнение редакции «Русского вестника» вообще: «Нельзя от картин требовать того, что Вы требуете. Это жанр, а жанр надо брать на одну мерку: искусен он или нет? Какие же тут проводить направления? Этак оно обратится в ярмо для искусства и удавит его, как быка давит веревка, привязанная к колесу. Потом: почему же лицо самого героя должно непременно стушевываться? Что это за требование? А Дон-Кихот, а Телемак, а Чичиков? Почему не идти рядом и среде и герою?»
Форма рассказа о приключениях «Очарованного странника» действительно напоминает и разъезды Чичикова по окрестным помещикам, и выезды Дон-Кихота в поисках соперников, и даже в какой-то мере роман Фенелона о странствованиях Телемака в поисках Одиссея. Ощутимо в «Очарованном страннике» и влияние народно-эпических русских былин. Материалом для этой повести, видимо, послужили Лескову его воспоминания и впечатления от службы в фирме Шкотт, действовавшей в Пензенской губернии. Так, например, ярмарка, на которой Иван Северьянович убил своего соперника, происходит в Пензе; о графах К. (Каменских) Лесков мог слышать еще в детстве, и т. д.
Среди разнообразных приключений Ивана Северьяновича два эпизода являются основными: плен у киргизов и история цыганки Груши и любви к ней Ивана Северьяновича. В этих эпизодах эпопеи «Очарованного странника» Лесков воскрешает темы и образы русской романтической литературы 1820-1830-х годов. Такое «воскрешение» романтики было характерным явлением в литературе начала 1870-х годов. Так, Тургенев в рассказе «Конец Чертопханова» (1872) воспроизвел основные мотивы из «Бэлы» Лермонтова: тургеневский герой, Чертопханов любит Машу, как Печорин; а своей страстной привязанностью к лошади он во многом напоминает лермонтовского Казбича. Привязанность к лошади оказывается у Чертопханова сильнее любви к цыганке.
Лесков в «Очарованном страннике» в отношениях князя и Груши воспроизводит основную психологическую коллизию той же повести Лермонтова: любовь князя и Груши проходит те же стадии, что и пылкое, но недолгое увлечение Печорина Бэлой.
«Страстью» к лошадям наполнена душа Ивана Северьяновича до тех пор, пока его не вытесняет глубокая привязанность к Груше. Сочетание этих двух чувств у Чертопханова и у Ивана Северьяновича говорит о том, что Лесков создавал своего героя с несомненной оглядкой на тургеневский персонаж, а князь у Лескова является очень сниженным, прозаическим вариантом лермонтовского Печорина.
Другой значительный эпизод «Очарованного странника» также возрождает одну из наиболее распространенных в романтической литературе 1820-1830-х годов тему — тему «пленника». После «Кавказского пленника» Пушкина русская литература была наводнена десятками различных «пленников». Среди них выделился и сюжет «киргизского пленника», разработанный в поэме Н. Муравьева (1828) и в романе Ф. Булгарина «Петр Выжигин» (1831). Воскрешая эту тему («плен у киргизов») в рассказе о странствованиях Ивана Северьяновича, Лесков имел перед глазами пример Л. Н. Толстого, в 1872 году напечатавшего («Заря», № 2) рассказ «Кавказский пленник», в котором высокая романтическая тема изложена языком человека из народа.
Такая художественная перекличка Лескова с Лермонтовым, Тургеневым и Толстым не могла быть случайным явлением в его творчестве. Она — свидетельство того, что Лесков как художник чувствовал себя в силах браться за разработку тем, уже затронутых его великими предшественниками и современниками.