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