Вскоре после отшельничества на Петровском острове обстоятельства переменились к лучшему. Заработок в различных изданиях увеличился, и юная пара перебралась в Петербург, где повела жизнь на широкую ногу, к чему Всеволод Владимирович всегда имел слабость. В то же время он начал помогать своей матери, что и делал в продолжение всей жизни.
Все это время и в последующие годы, изучая типы Петербурга и публикуя очерки «Фотографические карточки» и «Золотопромышленники», Всеволод Владимирович носился с одной идеей, которая стала его задушевной и любимой мечтой — написать роман из петербургской жизни, который дал бы полную картину жизни столицы от раззолоченных гостиных до притонов пьянства, разврата и нищеты. На эту идею натолкнул Всеволода Владимировича еще в 1858 году случай, в бытность его в университете, когда он случайно стал свидетелем возмутительной сцены избиения пьяным оборванцем какой-то ему подобной женщины, которая, отбиваясь от него, пересыпала отборные русские ругательства французскими фразами. Это навело на мысль, что избитая женщина была когда-то совсем иным существом. Как она дошла до такого состояния? Что была за среда, где могли иметь место такие безобразные сцены? Вот были первые вопросы, толкнувшие наблюдательного юношу в область исследований по этой интересной, неожиданно вставшей перед ним проблеме. Шесть лет работал Крестовский над изучением петербургских типов, готовясь к своему громадному произведению, и как результат этого — роман «Петербургские трущобы», законченный к 1864 году.
Изучая нравы Петербурга, Крестовский проникал в такие трущобы, посещение которых было бы для него небезопасно, если бы его не сопровождал в этих прогулках начальник сыскной полиции И.Д. Путилин. Генерал-губернатор Петербурга светлейший князь Суворов, узнав о новой страсти и таланте молодого литератора, дал ему carte blanche на посещение тюрем, больниц и других учреждений и предписал полиции содействовать ему в его наблюдениях, командируя сыщиков в его распоряжение. Прокурор Петербурга открыл для Всеволода Владимировича судебные архивы.
В 1864 году роман «Петербургские трущобы» начал печататься в «Отечественных записках» у А.А. Краевского. Успех его в русском обществе был громадный и роман занял исключительное своеобразное положение, являясь единственным в своем роде произведением. Мир явлений, в нем выведенный, был чрезвычайно сложным и занимательным уже потому, что все отношения героев и персонажей были рассмотрены с точки зрения грубых страстей, царящих во всяком обществе и действующих так разлагающе. Какой гуманной целью задался автор, явствует из следующих его слов: «Если мой роман заставит читателя призадуматься о жизни и участи петербургского бедняка и отверженной парии — трущобной женщины; если в среде наших филантропов и в среде администрации он возбудит хотя малейшее существенное внимание к изображенной мной жизни, я буду много вознагражден сознанием того, что труд мой, кроме развлечения для читателя, принес еще и частицу существенной пользы…»
Увлекаясь горячим сочувствием к бедности, Крестовский наметил себе цель — сопоставить благоденствие высших классов общества с бедствием нищих. Роман-хроника должен был объять все общественные элементы столицы. Интрига вышла чрезвычайно сложной, запутанной, но интересной, действие романа перевесило изображение действующих лиц, интрига — характеристику их, для занимательного начала и прекрасной середины пришлось придумать искусственный конец, который и навлек на роман главные нарекания критиков. Тем не менее он обладал столь положительными достоинствами, что привлек к себе редкое внимание буквально всей России. Впечатление, произведенное «Петербургскими трущобами» на публику, было так сильно, что одно время стало модным устраивать экскурсии в притоны и вертепы, описанные в романе.
Все эффекты, придающие роману несколько бульварный характер, меркнут перед захватывающим трагическим интересом к изображенным в нем правдивым картинам преступлений и разврата, сопровождаемым глубокими мыслями и выводами. «Петербургские трущобы» являли тем больший интерес для столичного общества, что многие типы были взяты автором из жизни и были списаны с известных всему Петербургу лиц.
Здесь следует коротко остановиться на нелепости возведенного на покойного писателя обвинения журналом «Сын Отечества» присвоения авторства этого романа, написанного якобы Н.Г. Помяловским. Кроме ярких вышеприведенных фактов, видна резкая разница в слоге обоих писателей, но самым важным опровергающим фактом является целый ряд свидетельств. Одним из важных свидетельств являются напечатанные в «Историческом вестнике» воспоминания И.К. Маркузе, работавшего у Крестовского и стенографически записывающего целые главы этого романа. Всеволод Владимирович диктовал И.К. Маркузе текст, в связи с чем последний жил полгода на квартире у Крестовского. Интересен рассказ М.С. Лескова о совместном посещении с Крестовским и М.О. Микешиным одного из притонов «Вяземской лавры», так называемого «Малинника», который появился в «Петербургской газете» после выхода «Сына отечества» и был подтвержден М.О. Микешиным в той же газете, рассказавшим о намерении автора издать роман иллюстрированным, для чего самим Микешиным уже была подготовлена целая коллекция рисунков. Начальник сыскной полиции И.Д. Путилин, с жаром заступаясь за Крестовского, писал: «От первой до последней строчки роман принадлежит Крестовскому. Я сам сопровождал его по трущобам, вместе с ним переодеваясь в нищенское платье. Наконец, я самолично давал ему для выписок дела сыскного отделения, которыми он широко пользовался, потому что почти все действующие лица его произведения — живые, существовавшие люди, известные ему так же близко, как и мне».
Кроме того, Крестовским оставлена рукопись романа, несколько записных книжек и талантливые наброски карандашом, сделанные рукою М.О. Микешина и самого Крестовского. Н.Г. Помяловского действительно часто можно было встретить в трущобных кабаках, однако появлялся он там из-за своей развившейся пагубной страсти к спиртному и не собирался извлекать из своих похождений литературной пользы, как свидетельствовал тот же И.Д. Путилин. Из этого видно, как гнусна была клевета, старавшаяся очернить Всеволода Владимировича не только как писателя, но и как человека, приписывая ему такие низкие качества души, которым не поверил бы никто знавший его честный, неподкупный и не способный ни на какую фальшь характер. Тот же И.К. Маркузе в своих воспоминаниях дает полный портрет писателя в период создания «Петербургских трущоб».
«Всеволод Владимирович был малоречив, серьезен и сдержан, не одушевлялся даже в кругу друзей; он прислушивался к тому, что говорили окружающие, сам же, если вступал в общую беседу, то лишь для того, чтобы бросить краткое замечание, выраженное сжато и просто. Покашливая нервным коротким кашлем, приобретенным скорее привычкой, чем вследствие какого-либо болезненного недостатка, играя не покидавшим его никогда моноклем, сидел он между собеседниками всегда внимательный ко всем, приветливый, но необщительный. Таков он был по природе, холодная сдержанность его не была рисовкой и он не позировал ею, но она была заметна в нем даже в минуты веселого настроения. Это свойство укоренилось в нем, быть может, с детства, проведенного им не в родной семье, вдали от нее, между чужими. Оно, впрочем, не имело ничего отталкивающего, не отчуждало его от общества и не заставляло уходить в самого себя. Напротив того, он любил общество, однако, в силу ли этой сдержанности, или вследствие быть может, застенчивой скромности, стушевывался в нем. Богатая одаренность, живая впечатлительность и артистическая оживленность его заставляли обращать на него внимание, выдвигали его иногда на первый план; но это происходило вопреки его намерению и претило ему. Так, например, он делался быстро в любом салоне тем, что называют „душою общества“, читал, рассказывал шутки, пел, но также быстро утрачивал это преимущество, так как легко уступал первенство другим. Необщительный вообще, он не любил сплетню, не передавал другим ходячих пересуд, за что особенно ценился друзьями, знавшими, что могут на него положиться и что он никого не выдаст.