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