К началу семидесятых годов, после явной неудачи романа «На ножах», Н. С. Лесков оставляет этот жанр и стремится утвердить права того литературного рода, который стихийно складывался в его творчестве. С этим периодом совпал и заметный перелом в мировоззрении Лескова. Он оказался как бы на распутье: еще не порвана связь с церковью, но в то же время писатель не только с болью критикует положение и состояние православной церкви, но уже становится на путь, который приведет его в конце жизни к принятию нравственного учения Л. Н. Толстого.
Из писем Б. Маркевича М. Н. Каткову выясняется, как дорожило Лесковым катковское окружение в начале 1873 года и как пыталось сохранить писателя для себя в момент выявившегося расхождения сторон. 25 марта, когда в редакции находились «Черноземный Телемак» и «Монашеские острова…», Маркевич, пытаясь предотвратить разрыв, писал Каткову о тяжелом семейном положении писателя: «Позвольте просить Вас помочь бедному Лескову; у него чуть не умер мальчик, которого он страстно любит, и хотя теперь опасность прошла, но ребенок требует серьезного лечения. А в доме теперь Ни гроша». Письмо Марковича Каткову от 15 мая 1873 года почти все посвящено «Очарованному страннику»: «Мне очень больно было узнать, что Вы признали неудобным напечатать рассказ Лескова, находящийся ныне у Вас. Рассказ этот читан был им нынешней зимой у Кушелева, в присутствии многих дам и любителей литературы, произвел на Всех, В том числе и на меня, самое прекрасное впечатление. Очень досадно то, что Лесков, совершенно смущенный этим отказом Вашим, может отдать эту вещь Суворину для помещения ее в «Вестнике Европы». Так как он живет единственно литературным трудом, мы не будем вправе сетовать на него за это».
Отказ в публикации рассказа огорчил Лескова. Разрыв писателя с М. Н. Катковым и его журналом становился почти неизбежным.
Именно в эти годы создаются произведения, которые войдут в будущий цикл легенд о русских праведниках: роман «Соборяне» (1872), повести «Запечатленный ангел» (1873) и «Очарованный странник» (1872-1873).
Сам Лесков не разделял оценку повести, данную Катковым. Об этом свидетельствует, например, его письмо Шебальскому: «За критику благодарю и «приемлю оную за благо, но не совсем разделяю и не вовсе ею убеждаюсь, а почему так? – о том говорить долго. Скажу Одно: Нельзя от картин требовать того, что Вы требууете. Это Жанр, А жанр надо брать за одну мерку: искусен он или нет? Какие же тут проводить направления? Эдак оно превратится в ярмо для искусства и удавит
И очерк, и рассказ были посланы в Москву в редакцию «Русского вестника». С «Монашескими островами…» дело затянулось, и печатание очерка было отложено, а о рассказе сотрудник редакции журнала Н. А. Любимов писал автору: «Многоуважаемый Николай Семенович, Михаил Никифорович (М. Н. Катков – главный редактор журнала «Русский вестник» – И. Б.) прочел «Черноземного Телемака» и после колебаний пришел к заключению, что печатать эту вещь будет неудобно. Не говоря о некоторых эпизодах, как, например, о Филарете и св. Сергии, вся вещь кажется ему скорее сырым материалом для выделки фигур, теперь весьма туманных, чем выделанным описанием чего-либо в действительности возможного и происходящего. Передаю вам, конечно, не в полной точности, что говорил Михаил Никифорович, а в самых общих выражениях. Он советует вам подождать печатать эту вещь, самый мотив которой может, по его мнению, выделаться во что-то хорошее».
По воспоминаниям А. Н. Лескова, сына писателя, это «широко эпопейное» произведение ценилось автором «до последних лет». Впервые повесть была опубликована в газете «Русский мир», где она и прошла с 15 октября по 23 ноября 1873 года под заглавием «Очарованный странник, его жизнь, опыты, мнения и приключения. Рассказ. Посвящается Сергею Егоровичу Кушелеву». Посвящение повести С. Е. Кушелеву имело свое объяснение: «дебют» повести Лескова в свете состоялся именно в кушелевском доме.
Летом 1872 года Лесков совершил путешествие по Ладожскому озеру, во время которого посетил Корелу, острова Коневиц и Валаам. «В незыблемой твердыне русского иночества, пребывающего здесь во всей чистоте древней христианской общины» («Монашеские острова на Ладожском озере»), рождался замысел рассказа о русском страннике. Результатом поездки явились очерк «Монашеские острова на Ладожском озере» и рассказ «Черноземный Телемак» (первоначальное название повести «Очарованный странник»).