Он много читал, посещал лекции в университете, знакомился с сочинениями Герцена, Фейербаха, Канта, Гегеля, Оуэна, с украинской и польской литературой. В Киеве произошла встреча с основоположником русской статистики Дмитрием Журавским, выкупавшим крепостных в ущерб своим материальным выгодам. Это знакомство повлияло на формирование гражданских взглядов писателя.
Оставив в 1857 году государственную службу и устроившись в частную коммерческую компанию А. Я. Шкотта, Лесков много ездил. Впечатления, полученные во время этих поездок, дали ему богатейший материал для творчества. В старости, отвечая на вопрос журналиста: «Где вы черпаете материал для ваших произведений?» – Лесков сказал, указывая на свой лоб: «Вот из этого сундука. Здесь хранятся впечатления шести-семи лет моей коммерческой службы, когда мне приходилось по делам странствовать по России, это самое лучшее время моей жизни, когда я много видел и жил легко».
Журналистским дебютом писателя стала серия статей экономического и социально-бытового характера достаточно резкого, обличительного содержания. Определяя значение литературного слова, Лесков писал: «Пора нам отвыкать от мысли, что предметом литературы должно быть что-нибудь особенное, а не то, что всегда перед глазами и от чего мы все страдаем прямо или косвенно. Сбросив вековой хлам предупреждений, мы ощутим себя близким к жизни наших меньших братии и сумеем помочь им вовремя и кстати, обнаруживая противящиеся гигиене стороны общественной жизни». Эти статьи дорого обошлись писателю, обвиненному в клевете и по лжесвидетельству во взятке. Дело прекратили, но Киев пришлось покинуть.
В 1861 году Лесков переезжает в «самый умный город в стране» – Петербург, чтобы целиком отдать себя тому делу, которому он посвятит всю дальнейшую жизнь. Будущий писатель печатается в «Отечественных записках», работает в газете «Северная пчела», пишет для московского еженедельника «Русская речь».
Царский манифест 1861 года Лесков воспринимает как начало реформ. Раскол общественной мысли на либеральное и революционно-демократическое течение приводит его к «постепеновцам», умеренность которых казалась ему более надежной. Хотя он являлся безусловным сторонником широких реформ и искоренения остатков крепостнического строя, но мысль о том, что объятый предрассудками народ способен реально изменить общество, не была близка писателю, о чем он и спорил с «Современником».
В 1862 году в журнале «Век» было напечатано первое произведение писателя – рассказ «Погасшее дело».
Вслед за ним в других журналах появляются: «Разбойник» (1862), «В тарантасе» (1862), «Овцебык» (1862), «Язвительный» (1863). Многие ранние произведения Лескова написаны в жанре художественного очерка.В 1864 году в журнале «Библиотека для чтения» был напечатан роман «Некуда»,
в котором он пытался посрамить нигилистов, показал трудности революционной борьбы и высказал мысль о бесперспективности революционного движения в России 60-х годов. «Антинигилистический» роман вызвал возмущение в передовых литературных кругах, был даже пущен слух, что он написан по заказу III Отделения. Один из рецензентов признавался: «…г. Лесков имеет такую литературную репутацию, что хвалить его своего рода смелость». В художественном отношении произведение было достаточно незрелым. «Роман этот носит в себе все знаки спешности и неумелости моей», – заметил впоследствии сам писатель.В центре ряда ранних произведений писателя оказывается женский характер, трагическая судьба женщины: «Житие одной бабы»
(1863), «Леди Макбет Мценского уезда» (1865), «Воительница» (1866). Тема женской судьбы – одна из актуальных в прогрессивной литературе 60-х годов, и Лесков решает ее с глубоким сочувствием к русской женщине. В повестях нарисованы драматичные образы женщин разных сословий: крестьянки, провинциальной купчихи, провинциальной интеллигентки.