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