Кушелев хлопотал о месте для Лескова в Министерстве народного просвещения. К хлопотам присоединились и другие лесковские знакомые: еще не успевший разойтись с автором «Соборян» Михаил Никифорович Катков – он был на короткой ноге с Дмитрием Андреевичем Толстым, сменившим Головнина на министерском посту, а также симпатизировавший Лескову граф Алексей Константинович Толстой, имевший широкие связи в свете. Мрежи (сети), закинутые Кушелевым и остальными в море житейское, принесли улов. Место было найдено.

Вскоре Лесков уже ехал представляться Д. А. Толстому как будущий сотрудник министерства. Маркевич и другие знакомые настоятельно советовали сшить для такого важного свидания вицмундир, но Лесков уперся: «…я не в департаментские чиновники иду, а в члены Ученого комитета»⁷⁰⁶. Формально он был прав, однако негласные законы всё же требовали мундира – зримого знака лояльности. На встрече граф Толстой, увидев соискателя в обычном сюртуке, и бровью не повел, был благожелателен и любезен и оставил у него самое благоприятное впечатление. Андрей Николаевич Лесков не сомневался, что отменно воспитанный Толстой умело скрыл свое истинное отношение к свободолюбивому писателю, с которым к тому же встретился не совсем по своей воле.

Но некоторые резоны не шить мундир у Лескова действительно были. До этого он дважды пытался попасть к министру на прием. Первый раз – в марте 1868 года: он написал Толстому, что хотел бы сказать «несколько слов», обещая уложиться в пять минут⁷⁰⁷. Просителю было отвечено, что «г. министр нездоров». Зачем Лескову понадобилась аудиенция, да еще всего на пять минут, неизвестно. Неудивительно, что Толстой на эту невнятицу откликнуться не пожелал.

Второй раз Лесков обратился к Дмитрию Андреевичу, занимавшему тогда еще и должность обер-прокурора Святейшего синода, в декабре 1872 года с докладной запиской, в которой излагал уже конкретную просьбу:

«Литератор Н. С. Лесков, чувствуя ревностное желание послужить интересам русской Церкви и имея близкое знакомство с бытовою стороною нашего клира, ходатайствует у Его сиятельства о принятии его, Лескова, на службу по Святейшему синоду. Николай Лесков. Адрес Лескова: СПб., Фурштатская, № 62»708.

«Литератор Н. С. Лесков, чувствуя ревностное желание послужить интересам русской Церкви и имея близкое знакомство с бытовою стороною нашего клира, ходатайствует у Его сиятельства о принятии его, Лескова, на службу по Святейшему синоду. Николай Лесков. Адрес Лескова: СПб., Фурштатская, № 62»⁷⁰⁸.

Толстой приказал разузнать, что из себя представляет проситель, и даже встретился с ним 4 января 1873 года, но на службу в Синод так и не принял.