Тем временем Гней Юлий Агрикола, наместник Британии, уже известный своим участием в военных операциях в Уэльсе и южной Шотландии во времена предыдущего императора, предпринял три удачных похода в Каледонию и победил в сражении в Гравпиевых горах нынешнее графство Абердиншир). В 85 г. Агриколу вызвали в Рим благодаря усилиям его горячего почитателя и зятя, Тацита, который терпеть не мог императора (возможно, из-за того, что испытывал угрызения совести за высокий пост, полученный от него). Историк утверждал, что победа в Гравпиевых горах не заслуживала никакого триумфа, поскольку на самом деле никаких земель не было захвачено.
Следующей, еще более честолюбивой целью Домициана стала Дакия, ослабевшая в последнее столетие, но теперь воспрянувшая под управлением царя Децебала, в 85 г. переправившегося через Данувий и убившего Оппия Сабина, наместника Мезии. Собрав подкрепления, Домициан сам отправился к театру военных действий, но на следующий год вернулся в Рим. Тем временем его войска вновь потерпели поражение, причем на сей раз в бою пал префект претория Корнелий Фуск. И все-таки в 88 г. подтвердилось превосходство римлян — под командованием Теттия Юлиана они одержали победу в битве при Тапе, недалеко от столицы Дакии, Сармизегетусе. После Столетних Игр в Риме Домициан отметил этот успех Триумфом.
Однако подобный ход событий не мог продолжаться вечно. Так, в 89 г. — в год только что упомянутого Триумфа — среди римских войск в Верхней Германии (в легионе под командованием Луция Антония Сатурнина) вспыхнул опасный вооруженный мятеж. По слухам, поводом стал гомосексуализм Сатурнина, в то время как Домициан проявлял пуританское неодобрение к подобным пристрастиям. Сатурнин заключил союз с недовольными сенаторами, которые не любили и боялись императора. Завладев казной двух легионов Могунциака, Сатурнин заставил их провозгласить себя императором, а его единомышленники в Германии подняли восстание. Но командующий Нижней Германии Лаппий Максим выступил против узурпатора, и в битве у форта Кастелл Сатурнин был убит. Сам же Домициан поспешно выступил из Рима и появился здесь чуть позже, и самовольно учинившие сражение офицеры вместо благодарности получили наказание (хотя Лаппий Максим в надежде уменьшить кару убил дочерей Сатурнина). Уже через двадцать четыре дня после начала мятежа жрецы Рима отпраздновали победу.
После тщательной инспекции всех войск в Германии Домициан занялся данувийским фронтом, где назревали серьезные волнения среди германских племен маркоманнов, квадов и сарматских язигов. Чтобы развязать себе руки, ему пришлось отказаться от возможности развить успех Рима в войне с Дакией: когда Децебал предложил заключить мир, Домициан дал согласие. Освободившись от дакийской проблемы, он обрушился на язигов и разбил их, но не завершил разгром полностью, сочтя достигнутое достаточным для триумфа. Волнения в провинциях оказались предвестником грядущего кризиса у данувийской границы, которую германцы смяли в следующем столетии.
Домициан проводил много времени рядом с солдатами, и они платили ему любовью. А вот для управления центурионами ему пришлось учредить новую армейскую кадровую службу, которая собирала все записи и доклады о военачальниках и представляла императору обширные сведения для принятия решений о персональных назначениях, поощрениях и перемещениях. Это лишь один пример из множества решительных мер, тщательно продуманных его ясным разумом. Как отмечал Светоний, донесший до нас описание уродливой внешности Домициана, «столичных магистратов и провинциальных наместников он держал в узде так крепко, что никогда они не были честнее и справедливее». Как заметил один из величайших историков Древнего Рима, Теодор Моммзен, он был одним из лучших управленцев, возглавлявших Империю.
Однако его правление характеризовалось крайне аскетической суровостью и поистине ужасающим следованием букве закона. В 83 г. Домициан назначил трем жрицам богини Весты, виновным в аморальном поведении, предписанную традициями смертную казнь, а семь лет спустя главную жрицу того же ордена весталок, Корнелию, за тот же проступок заживо замуровали в подземной келье, тогда как ее любовников засекли розгами насмерть. Эти вселявшие ужас и смятение наказания явно противоречили сильному отвращению к кровопролитию, которое приписывали Домициану. Но они совершенно точно соответствовали религии античного Рима, вынуждавшей его придерживаться древних ритуалов с церемониальной пышностью. Ему было свойственно глубокое, почти мученическое почитание богини Минервы, которой особенно истово поклонялись на Сабинских холмах, откуда происходил его род. Именно этой богине, изображаемой с четырьмя лицами, посвящены многие выпуски монет времен Домициана; храм Минервы занял центральное место в новом императорском Форуме, Транситории (впоследствии — Форум Нервы).