Образ жизни его в это время был очень умеренный: рано вставая и ложась, он все свободное от службы время посвящал описанию военных действий. Сильная натура позволяла ему легко переносить всю тягость боевой и походной обстановки, и по вечерам он всегда находил сюжеты для анекдотов и рассказов, которыми развлекал и оживлял многочисленных и признательных слушателей. Будучи близким свидетелем штурма Плевны, он со свойственной ему картинностью изобразил его в своем романе «Тамара Бендавид», одного из героев которого, графа Каржоля, весьма кстати вывел в роли агента пресловутого товарищества «Грегор, Горниц и Коган», к деятельности которого мог достаточно присмотреться во время войны.
К 14 июля 1877 года вышли сразу два первых номера «Военно-летучего листка», который сообщал известия непосредственно с театра военных действий, давал сведения о потерях и наградах. Крестовский всюду следовал за главной квартирой, посетил Богот, Порадим, Пелишат и, живя в палатке, изнывая от палящей жары, неустанно работал, посылая кроме того корреспонденции в «Правительственный вестник» и телеграммы во многие газеты.
Государь император при чтении известий с театра войны, написанных Крестовским, почти всегда делал надпись: «Читал с особенным любопытством».
Однако пылкий по характеру Крестовский не был вполне доволен своим положением и постоянно просил у великого князя какой-нибудь командировки «в огонь», но получал категорический отказ, так как последний, особенно расположившись к Всеволоду Владимировичу после талантливых очерков из кавалерийской жизни, всячески его берег. Однако и он, наконец, уступил и согласился на прикомандирование Крестовского к Траянскому отряду генерала П.П. Карцева в качестве ординарца.
После двухдневных тяжелых работ по расчистке пути к Траянову перевалу на сильном морозе, которыми руководил Крестовский, не успев отдохнуть, он принял участие в ночном бою против турецких укреплений, венчавших вершину Траянова перевала на высоте нескольких тысяч футов, находясь во время горячей перестрелки в цепи батальона. После короткого перерыва, не оставляя занятые позиции, войска генерала Карцева взяли укрепления, с боем спустились с хребта и заняли селения Текке и Карнари.
Во всех этих боях генерал Карцев неоднократно посылал Крестовского на боевую линию, причем последний не щадил себя и поминутно рисковал жизнью.
Затем Крестовский участвовал в дальнейшем продвижении Траяновского отряда и направился с ним на Адрианополь и Демотику. Весь этот поход занял около трех недель — и впечатлительному Всеволоду Владимировичу пришлось быть свидетелем ужасов войны, порожденных поспешным бегством турок на юг страны при первом известии, что знамена нашей победоносной армии взвились на высотах неприступных Балкан.
В феврале Крестовский был снова командирован в авангардный отряд свиты его величества, причем во время блестящего рейда этого отряда, завершившегося взятием второй столицы Оттоманской Империи — Адрианополя, нес одновременно обязанности ординарца и вел летопись отряда, которая составила потом одно из лучших описаний эпизодов этой войны.
За отличие при штурме Плевны и при взятии Траянова перевала Крестовский был награжден орденами Святой Анны, Святого Владимира и Святого Станислава, кроме того, в эту кампанию он получил сербский орден Такова, румынский орден Fraceria Dunaria и черногорский орден князя Даниила.
V
Но вот окончилась война, и появился договор 19 февраля 1878 года, можно было вернуться в давно покинутую Россию. Переживая поочередно все чувства тоски по родине и радость возвращения и встречи с родными и близкими, Крестовский мог, наконец, вернувшись в Петербург, подумать о давно забытой им беллетристике.
Закованная в рамки походной и боевой деятельности фантазия художника не только не иссякла, но получила как бы избыток сил, с которыми и вырвалась при первой возможности наружу. Действительно, вскоре по возвращении из кампании, а именно в конце 1879 года, у Всеволода Владимировича зародилась идея большого романа-трилогии.