Из-за болезни Лесовского, с которым Вс.Крестовский служил на одном корабле, он полгода проводит в Японии. Результат этого - его двухтомная книга "В дальних водах и странах", а также написанный уже в Петербурге обстоятельный труд этнографически-статистического характера о положении и нуждах Южно-Уссурийского края.

Не успел Всеволод Владимирович оправиться от одного путешествия, как надо было собираться в новое, не менее далекое и экзотическое: его назначили старшим чиновником особых поручений при генерал-губернаторе Туркестана. Здесь он занимается приведением в порядок Ташкентской казенной библиотеки, раскопками в Афросиабе близ Самарканда, а также участвует в посольстве к эмиру Бухарскому. Последнее произвело на него сильное впечатление, в результате чего и появилась его новая книга "В гостях у эмира Бухарского", представляющая собой живые картины жизни Востока.

По окончании путешествия в Туркестан, где Всеволод Владимирович находит свое семейное счастье - женится на 20-летней дочери статского советника Евдокии Степановне Лагоде, его откомандировывают в распоряжение Министерства внутренних дел. Тут он вновь совершает два путешествия, но уже по России: одно по ознакомлению с деятельностью земства, другое - для осмотра промышленных и торговых центров России. Итогом их были статьи: "Под владычеством земства" и обзор "Промышленные и торговые центры России".

Однако на должности чиновника особых поручений Министерства внутренних дел он задержался недолго, и в 1887 году беспокойная судьба забросила его в департамент таможенных сборов. И вновь длительные поездки по железной дороге и на лошадях для инспектирования отдаленных бригад пограничной стражи, во время которых он изучал жизнь и быт офицеров и нижних чинов. Это изучение дало ему богатый материал для очерков: "Вдоль австрийской границы", "Русский город под австрийской маркой", "По закавказской границе".