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