За время своих архивных работ Всеволод Владимирович набрел на ряд неизвестных исторических фактов, результатом чего явилась его историческая повесть «Деды». 8 это время Крестовский сотрудничал в «Русском мире», издаваемом М.Г. Черняевым, который и дал ему идею написать исторический роман. М.Г. Черняев жил в то время на даче, имевшей историческое прошлое. Она принадлежала фрейлине Нелидовой, и император Павел, находясь у нее в гостях, именно там получил первое известие о смерти императрицы Екатерины II. Крестовский во время частых посещений М.Г. Черняева подробно осматривал дачу и навеянные ею образы и картины дали в результате повесть из времени императора Павла I. Главной целью и основной идеен писателя было фактически доказать, что мрачные стороны этого царствования были слишком преувеличены как современниками, так и последующими поколениями. Произведение это печаталось частями в «Русском мире», где Крестовский помещал также и свои передовые статьи.

В этот же период (1871–1876 гт.) он сотрудничал с В.В. Комаровым и часто посещал его вечера, находясь в дружбе с хозяином и писателями А.Ф. Писемским и Р.А. Фадеевым. С 1871 года Крестовский стал сотрудничать во вновь возникшем журнале «Нива», где поместил несколько своих рассказов: «На траве», «Пан Пшепендовский», «Мой собрат» и др.

К этому же времени относится публикование романа детективного жанра «Вне закона», основанием которого послужило громкое судебное дело.

В августе 1876 года Крестовский по распоряжению военного министра Д.А. Милютина был командирован в Варшаву для участия в торжествах по поводу вручения лейб-гвардии Уланскому полку его августейшим шефом нового Георгиевского штандарта с надписью «За сражение под Красным 5 декабря 1812 года», причем честью этой полк был обязан Всеволоду Владимировичу, разыскавшему в архиве подтверждающие подвиг полка документы. Товарищи уланы пиром чествовали своего историка и поднесли ему в знак признательности ценный подарок.

Между тем надвигалась Русско-турецкая война — началась мобилизация. Главнокомандующим армией на Европейском театре войны был назначен великий князь Николай Николаевич Старший. По личной воле государя императора Крестовский был командирован в действующую армию и на него было возложено редакторство «Военно-летучего листка» с пребыванием в главной квартире в Кишиневе, куда и прибыл Всеволод Владимирович.

Двадцать месяцев в действующей армии дали возможность Крестовскому составить массу очерков, которые в 1879 году были изданы отдельно и составили два больших тома.

Армия, стянутая к юго-западной границе России, была охвачена лихорадочным настроением из-за колебаний политического барометра. «Тут нет ни бахвальства, ни самонадеянности, ни кичливого презрения к своему противнику. Напротив, каждый солдат, каждый офицер смотрит весьма серьезно и скромно на предстоящее ему дело, не скрывает от себя его трудностей и почитает его за дело святое; недовольство же наше, которое проявляется, увы, слишком часто, имеет своим источником единственно лишь глубокое патриотическое чувство, которое дрожит от сомнения, что Россия отступит от своего святого дела с ущербом для ее достоинства», — писал в одном из своих писем из Кишинева Крестовский.

Походная типография, которой заведовал Всеволод Владимирович, помещалась в трех фургонах, которые следовали непосредственно за великим князем и его свитой, и имели право въезжать в огневую полосу. Этим правом всегда пользовался Крестовский, чтобы нагрузить в них запасы провизии и вина, которыми угощал всех, кого только встречал, и был истинным благодетелем в трудные минуты боевой обстановки.

Образ жизни его в это время был очень умеренный: рано вставая и ложась, он все свободное от службы время посвящал описанию военных действий. Сильная натура позволяла ему легко переносить всю тягость боевой и походной обстановки, и по вечерам он всегда находил сюжеты для анекдотов и рассказов, которыми развлекал и оживлял многочисленных и признательных слушателей. Будучи близким свидетелем штурма Плевны, он со свойственной ему картинностью изобразил его в своем романе «Тамара Бендавид», одного из героев которого, графа Каржоля, весьма кстати вывел в роли агента пресловутого товарищества «Грегор, Горниц и Коган», к деятельности которого мог достаточно присмотреться во время войны.

К 14 июля 1877 года вышли сразу два первых номера «Военно-летучего листка», который сообщал известия непосредственно с театра военных действий, давал сведения о потерях и наградах. Крестовский всюду следовал за главной квартирой, посетил Богот, Порадим, Пелишат и, живя в палатке, изнывая от палящей жары, неустанно работал, посылая кроме того корреспонденции в «Правительственный вестник» и телеграммы во многие газеты.

Государь император при чтении известий с театра войны, написанных Крестовским, почти всегда делал надпись: «Читал с особенным любопытством».

Однако пылкий по характеру Крестовский не был вполне доволен своим положением и постоянно просил у великого князя какой-нибудь командировки «в огонь», но получал категорический отказ, так как последний, особенно расположившись к Всеволоду Владимировичу после талантливых очерков из кавалерийской жизни, всячески его берег. Однако и он, наконец, уступил и согласился на прикомандирование Крестовского к Траянскому отряду генерала П.П. Карцева в качестве ординарца.

После двухдневных тяжелых работ по расчистке пути к Траянову перевалу на сильном морозе, которыми руководил Крестовский, не успев отдохнуть, он принял участие в ночном бою против турецких укреплений, венчавших вершину Траянова перевала на высоте нескольких тысяч футов, находясь во время горячей перестрелки в цепи батальона. После короткого перерыва, не оставляя занятые позиции, войска генерала Карцева взяли укрепления, с боем спустились с хребта и заняли селения Текке и Карнари.

Во всех этих боях генерал Карцев неоднократно посылал Крестовского на боевую линию, причем последний не щадил себя и поминутно рисковал жизнью.

Затем Крестовский участвовал в дальнейшем продвижении Траяновского отряда и направился с ним на Адрианополь и Демотику. Весь этот поход занял около трех недель — и впечатлительному Всеволоду Владимировичу пришлось быть свидетелем ужасов войны, порожденных поспешным бегством турок на юг страны при первом известии, что знамена нашей победоносной армии взвились на высотах неприступных Балкан.

В феврале Крестовский был снова командирован в авангардный отряд свиты его величества, причем во время блестящего рейда этого отряда, завершившегося взятием второй столицы Оттоманской Империи — Адрианополя, нес одновременно обязанности ординарца и вел летопись отряда, которая составила потом одно из лучших описаний эпизодов этой войны.

За отличие при штурме Плевны и при взятии Траянова перевала Крестовский был награжден орденами Святой Анны, Святого Владимира и Святого Станислава, кроме того, в эту кампанию он получил сербский орден Такова, румынский орден Fraceria Dunaria и черногорский орден князя Даниила.

Но вот окончилась война, и появился договор 19 февраля 1878 года, можно было вернуться в давно покинутую Россию. Переживая поочередно все чувства тоски по родине и радость возвращения и встречи с родными и близкими, Крестовский мог, наконец, вернувшись в Петербург, подумать о давно забытой им беллетристике.

Закованная в рамки походной и боевой деятельности фантазия художника не только не иссякла, но получила как бы избыток сил, с которыми и вырвалась при первой возможности наружу. Действительно, вскоре по возвращении из кампании, а именно в конце 1879 года, у Всеволода Владимировича зародилась идея большого романа-трилогии.

В предисловии к одному из своих, романов, желая установить для читателя ту точку зрения, с которой должно смотреть на него, В.В. Крестовский категорически заявляет: «Я никак не исключаю мою хронику из числа произведений тенденциозных, напротив, она имеет самую определенную тенденцию». Роману-трилогии «Тьма Египетская», «Тамара Бендавид» и «Торжество Ваала», увы, пришлось разделить судьбу тенденциозных произведений. Напечатать роман полностью в «Русском вестнике» стало возможным лишь после ухода М.Н. Каткова, когда редактором его стал Ф.Н. Берг. М.Н. Катков был очень встревожен основной мыслью романа о падении христианства в России. «По его (Каткова) словам у тебя выводится крещеная еврейка, которая, переходя из высших слоев общества в самые низменные, нигде не находит христианства в истинном смысле; так что выходит, что ей незачем было и креститься; а между тем еврейство оказывается на крепких устоях и все забирает силу…Дело в том, что массы и, в особенности, интеллигенция едва ли когда особенно выделялись над уровнем пассивного соблюдения христианства. Усилия просветительской деятельности представителей церкви и светских гуманистов заключались всегда в том, чтобы направлять в сторону пробуждения массы из их летаргии в этом отношении. Если же мы, вместо колеблющихся, особенно в наше время, представим им картину такого отчаянно безвыходного положения, то не будет ли это последним и может быть самым энергическим толчком в направлении наклонной плоскости?» — писал В.Н. Клюшников Крестовскому, излагая точку зрения редактора «Русского вестника» на замысел автора.