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