Вскоре Вс.Крестовский получает офицерский чин поручика. Начинается трудная полоса в его жизни. Во время бракоразводного процесса, так печально закончилось его супружество, присяжный поверенный оскорбил его. Крестовский вызвал чиновника на дуэль, и когда тот отказался драться, ударил его перчаткой по лицу, что вызвало новый судебный процесс, который Всеволод Владимирович выиграл. Но нападки либеральной прессы, последовавшие за процессом, он остро переживал. Тем более что инцидент с присяжным поверенным был только поводом, а причиной - все те же его антинигилистические романы.
Лучше складывались дела у Вс.Крестовского на военном поприще. Здесь на него посыпалось одно почетное поручение за другим. По желанию шефа полка великой княжны Марии Александровны он пишет историю Ямбургского полка, за что в качестве награды Александр II переводит его в лейб-гвардии Уланский его величества полк. Генерал-инспектор кавалерии великий князь Николай Николаевич сначала определяет Вс.Крестовского в комиссию по вопросу о преобразованиях в кавалерии, а затем поручает составление боевых летописей русской конницы. Однако император переводит служить Вс.Крестовского в гвардейский полк, шефом которого был он сам, и дает ему новое задание написать историю этого полка.
Работая в архивах, Всеволод Владимирович обнаружил ряд неизвестных ему ранее исторических фактов, которые легли в основу его повести "Деды" - о царствовании Павла I. В повести автор стремится доказать, что мрачные стороны царствования Павла I как современниками, так и последующими поколениями были сильно преувеличены.
Между тем началась русско-турецкая война, и Вс.Крестовского командировали в действующую армию корреспондентом "Правительственного вестника" и для редактирования "Военно-летучего листка". Статьи его, изданные затем отдельными книгами, составили два больших тома.
Однако роль летописца не совсем устраивает Крестовского, и после многочисленных просьб и настояний его прикомандировывают к Траянскому отряду генерала Карцева. Здесь он руководит расчисткой от снега дороги на Траянский перевал, а при штурме последнего в ночном бою находится в цепи 10-го стрелкового батальона.
После трехнедельного похода отряда генерала Карцева Вс.Крестовского командировали в авангардный отряд генерал-майора Струкова. Рейд этого отряда завершился взятием второй столицы Оттоманской империи - Андианополя. За турецкую кампанию Вс.Крестовский был награжден орденами Святой Анны 3-й степени с мечами, Святого Владимира 4-й степени с мечами и бантом, Сербским орденом Такова 4-й степени, румынским орденом Fraceria Dunariu и черногорским орденом князя Даниила 3-й степени.
По возвращении в Петербург Вс.Крестовский приступает к новому большому литературному труду - трилогии "Тьма Египетская", "Тамара Бендавид" и "Торжество Ваала". Всеволод Владимирович фундаментально готовился к написанию этого труда. Он изучал древнееврейский язык, делал нужные выписки из старых книг. Публикация первых глав "Тьмы Египетской" в "Русском вестнике" показала антиеврейскую направленность этого романа, так что редактор журнала М.Н.Катков отказался от дальнейшей публикации. И только когда редактором "Русского вестника" стал Ф.Н.Берг, были опубликованы все три романа, причем третий остался незаконченным из-за смерти автора.
Летом 1880 года Александр II отправляет Вс.Крестовского в новую командировку - на должность секретаря для военно-сухопутных сношений при главном начальнике русских морских сил в Тихом океане адмирале С.С.Лесовском. Одновременно он должен был вести исторические записки о плавании эскадры и писать корреспонденции в "Правительственный вестник" и "Военный сборник". По пути из Неаполя во Владивосток, куда Вс.Крестовский отправился вместе с адмиралом Лесовским, он побывал в Австрии и Италии.
Из-за болезни Лесовского, с которым Вс.Крестовский служил на одном корабле, он полгода проводит в Японии. Результат этого - его двухтомная книга "В дальних водах и странах", а также написанный уже в Петербурге обстоятельный труд этнографически-статистического характера о положении и нуждах Южно-Уссурийского края.
Не успел Всеволод Владимирович оправиться от одного путешествия, как надо было собираться в новое, не менее далекое и экзотическое: его назначили старшим чиновником особых поручений при генерал-губернаторе Туркестана. Здесь он занимается приведением в порядок Ташкентской казенной библиотеки, раскопками в Афросиабе близ Самарканда, а также участвует в посольстве к эмиру Бухарскому. Последнее произвело на него сильное впечатление, в результате чего и появилась его новая книга "В гостях у эмира Бухарского", представляющая собой живые картины жизни Востока.
По окончании путешествия в Туркестан, где Всеволод Владимирович находит свое семейное счастье - женится на 20-летней дочери статского советника Евдокии Степановне Лагоде, его откомандировывают в распоряжение Министерства внутренних дел. Тут он вновь совершает два путешествия, но уже по России: одно по ознакомлению с деятельностью земства, другое - для осмотра промышленных и торговых центров России. Итогом их были статьи: "Под владычеством земства" и обзор "Промышленные и торговые центры России".
Однако на должности чиновника особых поручений Министерства внутренних дел он задержался недолго, и в 1887 году беспокойная судьба забросила его в департамент таможенных сборов. И вновь длительные поездки по железной дороге и на лошадях для инспектирования отдаленных бригад пограничной стражи, во время которых он изучал жизнь и быт офицеров и нижних чинов. Это изучение дало ему богатый материал для очерков: "Вдоль австрийской границы", "Русский город под австрийской маркой", "По закавказской границе".
Служба в департаменте таможенных сборов с длительными поездками в малоосвоенные уголки страны была нелегкой для человека его возраста. Поэтому Вс.Крестовский с удовольствием принимает предложение Варшавского генерал-губернатора занять место редактора газеты "Варшавский дневник". И хотя по прибытии в Варшаву он энергично взялся за новое дело журналиста, работать ему было тяжело. На Крестовского обрушилась заграничная польская печать, не простившая ему "антипольских" романов "Две силы" и "Панургово стадо". Начались трения с цензором, которые угнетали Всеволода Владимировича настолько, что он не раз собирался оставить свой пост.