В том же году вышла повесть «Очарованный странник», произведение свободных форм, не имевшее законченного сюжета, построенное на сплетении разрозненных сюжетных линий. Лесков считал, что такой жанр должен заменить собой то, что принято было считать традиционным современным романом. Впоследствии отмечалось, что образ героя Ивана Флягина напоминает былинного Илью Муромца и символизирует «физическую и нравственную стойкость русского народа среди выпадающих на его долю страданий».

Если до тех пор произведения Лескова редактировались, то это было просто отвергнуто, и писателю пришлось публиковать его в разных номерах газеты. Не только Катков, но и «левые» критики враждебно восприняли повесть. В частности, критик Н. К. Михайловский указывал на «отсутствие какого бы то ни было центра», так что, по его словам, есть «…целый ряд фабул, нанизанных как бусы на нитку, и каждая бусинка сама по себе и может быть очень удобно вынута и заменена другою, а можно и еще сколько угодно бусин нанизать на ту же нитку».

После разрыва с Катковым материальное положение писателя (к этому времени женившегося вторично) ухудшилось. В январе 1874 года Н. С. Лесков был назначен членом особого отдела Ученого комитета министерства народного просвещения по рассмотрению книг, издаваемых для народа, с очень скромным окладом в 1000 рублей в год. В обязанности Лескова входило рецензирование книг на предмет, можно ли отправлять их в библиотеки и читальни. В 1875 году он ненадолго выехал за границу, не прекращая литературную работу.

«Праведники»

Создание галереи ярких положительных персонажей было продолжено писателем в сборнике рассказов, вышедшем под общим названием «Праведники» («Фигура», «Человек на часах», «Несмертельный Голован» и др.) Как отмечали впоследствии критики, лесковских праведников объединяют «прямодушие, бесстрашие, обостренная совестливость, неспособность примириться со злом». Заранее отвечая критикам на обвинения в некоторой идеализированности своих персонажей, Лесков утверждал, что его рассказы о «праведниках» носят большей частью характер воспоминаний (в частности, что о Головане ему рассказала бабушка, и т. д.), старался придать повествованию фон исторической достоверности, вводя в сюжет описания реально существовавших людей.

Как отмечали исследователи, некоторые свидетельства очевидцев, на которые ссылался писатель, являлись подлинными, другие были его же художественным вымыслом. Нередко Лесков обрабатывал старые рукописи и воспоминания. К примеру, в рассказе «Несмертельный Голован» использован «Прохладный вертоград» — лечебник XVII века. В 1884 году в письме в редакцию газеты «Варшавский дневник» он писал: Начало цитаты

В статьях вашей газеты сказано, что я большею частью списывал живые лица и передавал действительные истории. Кто бы ни был автор этих статей, он совершенно прав. У меня есть наблюдательность и, может быть, есть некоторая способность анализировать чувства и побуждения, но у меня мало фантазии. Я выдумываю тяжело и трудно, и потому я всегда нуждался в живых лицах, которые могли меня заинтересовать своим духовным содержанием. Они мною овладевали, и я старался воплощать их в рассказах, в основу которых тоже весьма часто клал действительно событие. Конец цитаты

Лесков (согласно воспоминаниям А. Н. Лескова) считал, что, создавая циклы о «русских антиках», он исполняет гоголевское завещание из «Выбранных мест из переписки с друзьями»: «Возвеличь в торжественном гимне незаметного труженика». В предисловии к первому из этих рассказов («Однодум», 1879) писатель так объяснил их появление: «Ужасно и несносно… видеть одну „дрянь“ в русской душе, ставшую главным предметом новой литературы, и… пошёл я искать праведных, <…> но куда я ни обращался, <…> все отвечали мне в том роде, что праведных людей не видывали, потому что все люди грешные, а так, кое-каких хороших людей и тот и другой знавали. Я и стал это записывать».