Происходили перемены и в личной жизни писателя. Еще в 1861 м году он женился на двадцатилетней актрисе Варваре Дмитриевне Гриневой. Женился по любви. Первое время молодые жили душа в душу, несмотря на финансовые трудности (Крестовский вступил в брак вопреки желанию родителей, считавших его неготовым к семейной жизни, и потому гордо отказался принимать от них какую-либо помощь). Позднее, благодаря литературным успехам, материальное положение значительно поправилось. У Крестовских родилась дочь — Маша (впоследствии тоже ставшая писательницей). Но вместе со славой Всеволода Владимировича росли и запросы его супруги. Варвара Дмитриевна считала, что, как жена известного литератора, она имеет право на большее, чем реально мог ей дать муж. На этой почве в семье начались размолвки, переросшие с течением времени в конфликт. В конце концов, супруги расстались.
Может быть под влиянием семейных неурядиц Крестовский решил поступить на военную службу. А перед этим он в своем творчестве невольно «пересекся» с биографией Тараса Шевченко (эпизод небезынтересный для шевченковедения). В 1867-м году писатель совершил большой путешествие по Волге, по впечатлениям которого написал несколько очерков. В одном из них — очерке «Сольгород», посвященном Нижнему Новгороду, Всеволод Владимирович разоблачил местного полицмейстера, взяточника и казнокрада Павла Лаппо-Старженецкого (изображенного под именем Загребистой Лапы). Того самого Лаппо-Старженецкого, которого Шевченко в «Дневнике» называет «нижегородским моим приятелем», «хорошим человеком», «бравым и любезным полицмейстером». Как известно, во время пребывания Тараса Григорьевича в Нижнем Новгороде, «любезный полицмейстер» «засвидетельствовал» (разумеется, не бесплатно) мнимую болезнь поэта, чем помог ему избежать нежелательной поездки в Оренбург. По этой причине и удостоился Лаппо-Старженецкий хвалебных отзывов и от «великого кобзаря», и от позднейших «шевченкознавцев». Крестовский придерживался иного мнения и выставил в «Сольгороде» полицейского хапугу и вора в истинном, крайне неприглядном виде.
Кстати сказать, будучи убежденным монархистом, Всеволод Крестовский не боялся критиковать тогдашние порядки. Критиковать недостатки для того, чтобы их устранить и, тем самым, усилить самодержавный строй. «Я остаюсь — и навсегда останусь — при глубоко неизменном убеждении, что прямое слово правды никогда не может подрывать и разрушать того, что законно и истинно, — писал он. — А если наносит оно вред и ущерб, то только одному злу и беззаконию». Этим Всеволод Владимирович разительно отличался от писателей советских, которые свою лояльность властям доказывали приукрашиванием, «лакировкой» действительности.
