Всеволод Владимирович Крестовский родился 11 февраля 1839 года в имении своей бабушки селе Березайка Тарашинского уезда Киевской губернии. Происходил он из старинного дворянского рода.

Отец его Владимир Васильевич, отставной улан, служил комиссаром при Петербургском военно-временном госпитале и из-за трудного материального положения согласился на переезд жены Марии Осиповны, урожденной Товбич, с сыном на жительство к бабушке. Так ранние годы детства и отрочества были проведены будущим писателем среди поэтической обстановки деревенской жизни в Малороссии. Будучи еще ребенком, он отличался редкой наблюдательностью, восприимчивостью и впечатлительностью. Отличительным качеством его характера была доброта: ребенком он выпрашивал у матери деньги для бедных, делился всеми лакомствами с дворовыми детьми, и это качество красной нитью прошло через всю его жизнь, и ни горький опыт, ни людская неблагодарность не успели зачерствить его чуткое ко всему доброму сердце. Память у него была редкая, и он быстро схватывал слышанное. Рано выучившись читать, он по целым дням предавался любимому занятию и быстро подготовился к поступлению в Первую Петербургскую гимназию, куда решили определить его родители. Мать В.В. Крестовского, умная и образованная женщина, сама занималась с сыном, кроме четырех учителей и гувернанток.

Каким же представлялось заведение, которое первым подготовило Всеволода Владимировича к его будущей деятельности? Первая Петербургская гимназия была преобразована из бывшего благородного пансиона при Петербургском университете и одна из немногих в Петербурге оставалась закрытым привилегированным заведением. Прием в нее был только для потомственных дворян; плата за воспитание повышенная, и вся обстановка жизни гимназистов была поставлена на более широкую ногу, чем в других гимназиях. Но этим, кажется, и ограничивались привилегии этой школы; все же недостатки, присущие системе воспитания того времени, находили там полное гражданство. В четырех младших классах свирепствовала розга как краеугольный камень воспитания. Состав гувернеров был более чем жалкий. Все это были иностранцы, без всякого образования, зачастую с темным прошлым, на редкость невежественные. Отношения между ними и гимназистами часто принимали характер междоусобной войны между угнетателями и угнетаемыми. Общей чертой того времени в деле педагогики было стремление примешивать ко всему политический элемент, и вот искоренение в воспитанниках этих «зловредных» идей, мешавших спокойно спать директорам и наставникам, и было главной задачей воспитания. Неважно, что в описываемую эпоху у воспитанников не только не было антигосударственных стремлений, а наоборот — большой подъем патриотизма благодаря славной Севастопольской обороне, так что многие из молодежи прямо со школьной скамьи отправлялись на обагренные русской кровью бастионы.

По выходе из университета Крестовский предался почти исключительно литературной деятельности. Любимым рестораном литераторов был в то время трактир Еремеева у Аничкова моста. Там Крестовский познакомился и сошелся с талантливым поэтом-сатириком Василием Степановичем Курочкиным, который только что начал издавать еженедельный журнал «Искра». Крестовский часто посещал вечера, на которые собирались сотрудники журнала и многие литераторы, приносил обыкновенно новые стихи и читал их перед собравшимися. Один из сотрудников журнала Н.П. Ломан, писавший под псевдонимом «Гнут», тут же сочинял пародию на них и вслух прочитывал ее под добродушный смех слушателей и самого автора.

В 1860 году Крестовский познакомился с семейством Сен-Лоран, глава и многие члены которого были военными. Это сближение в значительной мере развеяло предубеждение Крестовского против военной среды, бывшей тогда настолько непопулярной в обществе, что даже славная Севастопольская оборона не переменила взглядов на военных. Общество, увлеченное либеральными идеями, желало видеть всех своими сторонниками, и поэтому среда, исключающая возможность этого, подвергалась остракизму. Крестовский тоже несочувственно относился к «военщине» и, только познакомившись с внутренним миром и взглядами представителей семейства Сен-Лоран, мало-помалу стал менять свое мнение.

В это же время Крестовский встречается с Варварой Дмитриевной Гриневой, дочерью актрисы Санкт-Петербургских Императорских театров Екатерины Васильевны Гриневой. Красивая, живая, грациозная девушка, бывшая тогда тоже актрисой, сразу вскружила голову мечтательному юноше, и увлечение закончилось свадьбой, несмотря на молодость влюбленных: Крестовскому было тогда двадцать два года, невесте — двадцать лет. Венчание состоялось в Петербурге при небольшом числе друзей. Посаженным отцом был приятель жениха граф Г.А.Кушелев-Безбородко, основатель журнала «Русское слово».

За женой Всеволод Владимирович не получил ничего, кроме свадебного маленького приданого, для его родных свадьба не была желанной из-за его крайней молодости и болезненности. Крестовский всегда был горд тем, что ни у кого не хотел одалживаться и пришлось познакомиться с нуждой: из-за нее молодые переехали в пустую дачу на Петровском острове и оставались там до декабря. Но веселое беззаботное настроение не покидало супругов. Часто навещали их друзья, круг которых увеличился: к нему прибавились А.Н. Милюков, М.О. Микешин, К.Е. Маковский.

Вскоре после отшельничества на Петровском острове обстоятельства переменились к лучшему. Заработок в различных изданиях увеличился, и юная пара перебралась в Петербург, где повела жизнь на широкую ногу, к чему Всеволод Владимирович всегда имел слабость. В то же время он начал помогать своей матери, что и делал в продолжение всей жизни.