Оставив после двухлетнего пребывания Петербургский университет, Всеволод Крестовский начинает сотрудничество в журнале Ап. Григорьева "Русское слово", где в 1860 году появляются его повести "Пчельник" и "Сфинкс". Одновременно многие периодические издания публикуют его греческие переводы, оригинальные стихотворения, короткие рассказы и эскизы, так что уже к 1864 году молодой беллетрист получает известность среди столичной публики. Оценка его литературных произведений весьма полярна: от положительных рецензий до резко отрицательных, низводящих сочинения В. Крестовского в ранг "легковесных", "поверхностных". Как отмечал наиболее пристрастный из критиков, А. Скабичевский, "очевидно было, что плывя по течению, Крестовский не врезывался в него глубоко, а скользил по поверхности. Обо всех тревоживших в то время общество вопросах он судил с кондачка, придавая им вид беззаветной пошлости…" И тот же А. Скабичевский в своих "Литературных воспоминаниях" отмечал, что "как это ни странно, но я должен признаться, что первые семена свободомыслия посеял в меня автор "Панургова стада".
"Петербургские трущобы" начали публиковаться в журнале "Отечественные записки" в 1864 году и уже в 1867 году изданы отдельной книгой под названием "Петербургские трущобы, книга сытых и голодных, роман в шести частях, четыре тома". Они предварялись авторским вступлением: "Если мой роман заставит читателя призадуматься о жизни и участи петербургского бедняка и отверженной парии — трущобной женщины; если в среде наших филантропов и в среде административной он возбудит хотя бы малейшее существенное внимание к изображенной мною жизни, я буду много вознагражден сознанием того, что труд мой, кроме развлечения для читателя, принес еще и частицу существенной пользы для той жалкой, темной среды, где голодная мать должна воровать кусок хлеба для своего голодного ребенка; где источником существования двенадцати-тринадцатилетней девочки является нищенство и продажный разврат; где голодный и оборванный бедняк, тщетно искавший честной работы, нанимается для совершения преступления мошенником сытым и более комфортабельно обставленным в жизни, причем этот ничем почти не рискует, а тот, за самую ничтожную цену, ради требований своего непослушного желудка, гибнет на каторге; где, наконец, люди болеют, страдают, задыхаются в недостатке чистого, свежего воздуха и иногда решаются, если не на преступление, то на самоубийство, чем ни попало и как ни попало, лишь бы только избавиться от безнадежно-мрачного существования, буде до этого крайнего исхода не успеют зачерстветь и оскотиниться настолько, чтобы потерять всякую способность к каким бы то ни было человеческим ощущениям как нравственным, так и физическим, кроме инстинктов голода, сна и часто ненормально удовлетворяемой половой потребности. Здесь-то вот и кроется наша невидимая язва, здесь наша горькая скорбь вавилонская, которая даже не вопиет о спасении, об исходе, по причине очень простой и несложной: она их не знает".
"Петербургские трущобы", не оставившие равнодушными как либералов, так и консерваторов, — а нападки и тех и других были особенно яростными уже после смерти писателя — сочетают черты двух направлений, двух граничащих эпох в искусстве: свойственная юности писателя мягкосердечность и мечтательность роднит роман с эпохой романтизма, особенно в несколько искусственных драматических эффектах, некоторой вычурности в названиях глав; наблюдательность и большая добросовестность в анализе материала, сопричастность делали роман заметной вехой в реализме середины XIX столетия. Но, как это ни странно, ни радикалы, встретившие роман насмешливо и несколько презрительно, ни так называемые реакционеры не увидели в этом произведении тех основ, на которых зиждилось все творчество В. Крестовского, которые стали неотъемлимой частью его творчества: духовность, российское единство, христианство.
Совершенно нелепыми были обвинения, выдвинутые против уже покойного писателя в том, что он присвоил себе "Петербургские трущобы", якобы написанные Н. Помяловским, а самое интересное в этой истории было то, что ни один демократ и либерал не вступился за честь В. Крестовского. Вздорность этих обвинений была очевидной. Первым не выдержал Н. Маркузе, работавший с В. Крестовским во время написания этого романа, и стенографически записывавший целые его главы. Но наиболее характерными были свидетельства таких видных деятелей искусства, как Н. Лесков и М. Микешин, а также бывшего начальника сыскной полиции знаменитого И. Путилина.
"Это было летом, — вспоминал Н. Лесков, — мы втроем: Крестовский, я и еще кто-то, кажется, Микешин, впрочем наверно не помню, отправились гулять и встретили знакомого Крестовскому сыщика, который и предложил нам отправиться в "Малинник". Мы, конечно, охотно согласились. Пришли. Внутренность "Малинника" вы вероятно помните по описанию Крестовского. К нам сейчас же подсели местные дамы и потребовали угощения. Они пили водку, а мы ели яйца, единственное кушанье, которое мог рекомендовать нам буфетчик, хорошо знавший сыщика. Подсела к нашей компании и женщина, которую Крестовский назвал Крысой. Она без церемонии влезла на колени к бывшему со мною и Крестовским спутнику. Помню случившийся при этом небольшой, но довольно характерный эпизод: приятель наш сидел с Крысой и держал в руке, откинутой за спинку стула, папиросу. Кругом сидели и ходили самые отвратительные оборванцы. Один из них, проходя мимо нашего стола, преспокойно схватил эту папиросу и начал курить. Спутник наш вскочил и собирался проучить нахала. Однако сыщик удержал его, говоря, что затевать скандал здесь опасно. Когда этот инцидент закончился, нас повели по какому-то длиннейшему коридору смотреть внутренние помещения "Малинника". Шли мы совершенно спокойно, как вдруг где-то сзади послышался сначала сильный шум, точно от падения на пол какого-то большого тела, потом крики: "Помогите, режут, убивают!"
— Обыкновенная история, — заметил сыщик, — это бывает здесь.
Он не успел окончить начатой фразы, как крики о помощи сменились другими: "Спасайтесь, полиция!" Мы обернулись, и представьте себе наше удивление. Коридора уже не было, мы находились в комнате: сзади нас спустилась сверху стена, и коридор превратился в комнату. Вышли мы из "Малинника" совершенно другим ходом — нас вывел сыщик".
Вскоре в "Петербургской газете" появилось еще одно свидетельство того же H. Лескова; "Расскажу вам еще эпизод, также подтверждающий мои слова о том, что "Петербургские трущобы" от первой до последней главы написаны Крестовским. Депо было зимою. Всеволод в то время ходил в енотовой шубе, до такой степени старой, что он сам не называл ее иначе, как "Енотавр". Енотавр этот он накидывал на носимую им постоянно куртку из верблюжьего сукна, а голову покрывал пробковой шляпой. И так шел он однажды по набережной от Аполлона Григорьева ко мне. Погода была холодная, ветряная, он поскользнулся и упал, да так, что енотавр полетел в одну сторону, а пробковая шляпа в другую. Во время этого падения из шубы вывалилась рукопись какой-то части "Петербургских трущоб", и листы ее рассеялись по ветру. Собрать их Всеволод не мог, и пришлось писать эту часть снова".
Свидетельства Н. Лескова были подтверждены и скульптором, художником М. Микешиным, появилось это подтверждение в той же "Петербургской газете": "С удовольствием подтверждаю слова даровитого Николая Семеновича Лескова; мы втроем: Вс. Крестовский, Лесков (тогда носивший псевдоним Стебницкий) и я ходили в Вяземскую Лавру и в "Малинник", изучали трущобы и намеревались издать их иллюстрированными, для чего мною была уже и зачерчена небезынтересная коллекция разных несчастных типов, но отъезд мой тогда за границу оставил дело иллюстрации к "Трущобам" неосуществленным".