Кандидатур на её замещение оказалось несколько, но в военном министерстве предпочтение выказали генерал-лейтенанту Юденичу. Получив в соответствии с императорским указом от 25 января 1913 года новое назначение, Николай Николаевич после коротких сборов убыл на новое место службы в город Тифлис. Там располагался штаб Кавказского военного округа и управление недавно восстановленного царского наместничества на Кавказе.
Его встреча с генералом от кавалерии и генерал-адъютантом, графом Илларионом Ивановичем Воронцовым-Дашковым была исключительно тёплой и приятной. Кавказский наместник Его Императорского Величества по совместительству являлся ещё и главнокомандующим войсками Кавказского военного округа и войсковым походным атаманом Кавказских казачьих войск — Кубанского и Терского.
Юденич был много наслышан о Воронцове-Дашкове, умелом администраторе, так много сделавшим для развития Кавказского края и человеке там весьма уважаемом. Один из крупнейших землевладельцев России, военного образования он не имел, учился в Московском университете. С началом Крымской войны ушёл добровольцем в русскую армию, службу начал в лейб-гвардии Конном полку.
В последние годы Кавказской войны молодой граф командовал личным конвоем князя А. И. Барятинского. Имел за боевые заслуги орден Святого Георгия 4-й степени (за штурм крепости Ура-Тоби) и наградное золотое оружие. Воевал против горцев имама Шамиля и в Туркестане. В 29 лет близкий друг будущего императора Александра III получил звание генерал-лейтенанта, командовал лейб-гвардии Гусарским полком.
В ходе Русско-турецкой войны 1877-1878 годов начальствовал на болгарской земле над кавалерией Рущукского отряда (за исключением казачьей). После войны командовал в столичном гарнизоне 2-й Гвардейской кавалерийской дивизией.
Взлёт Воронцова-Дашкова по служебной лестнице начался с воцарением на престоле Александра III Александровича, с которым он сдружился во время войны на болгарской земле. Тогда цесаревич-наследник стоял во главе Рущукского отряда. Высокие назначения следовали один за другим — главноуправляющий государственного коннозаводства, министр императорского двора и уделов, канцлер Российских Царских и Императорских орденов, член Государственного совета России. После убийства государя Александра II граф некоторое время был начальником царской охраны и одним из организаторов «Священной дружины».
После восстановления поста царского наместника на Кавказе, в феврале 1905 года, Илларион Иванович Воронцов-Дашков оказался в Тифлисе. Он оказался тем государственным мужем императорской России, который лично много сделал для развития Кавказского края. Один из его известных современников С. Ю. Витте писал о нём:
«Быть может, он единственный из сановников на всю Россию, который и в настоящее время находится в том краю, в котором управлял, и который пользуется всеобщим уважением и всеобщей симпатией...
Это, может быть, единственный из начальников края, который в течение всей революции, в то время, когда в Тифлисе ежедневно кого-нибудь убивали или в кого-нибудь кидали бомбу, спокойно ездил по городу как в коляске, так и верхом, и в течение всего этого времени на него не только не было сделано покушения, но даже никто никогда ещё не оскорбил ни словом, ни жестом».
Воронцов-Дашков самым добросовестным образом осуществлял исполнение своих наместнических обязанностей, в том числе и главы расквартированных здесь войск, на всегда неспокойном Кавказе. Ему требовались деятельные и надёжные помощники, и он поэтому был откровенно рад прибытию нового начальника окружного штаба:
— Я рад вас видеть, Николай Николаевич, на кавказской земле, в нашем Тифлисе.
— Благодарю, ваше превосходительство.
— Мне государь император нарочным прислал письмо, в котором уведомлял о вашем назначении. Могу сообщить, что государь о вас высокого мнения.
— Весьма признателен государю за доброе слово.
— Вы, как известно мне, на Кавказе ещё не служили за тридцать лет вашей службы в русской армии?
— Нет, не приходилось. Учился в Москве, служил в Варшаве, столице, Туркестане, воевал в Маньчжурии. Потом оказался в Казани.
— У вас, Николай Николаевич, хороший послужной список. Но замечу, что на Кавказе будет потруднее, чем в Туркестане или в Казани. Тем более, по всем приметам, приближается большая война.
— Да, мне об этом сказал при представлении наш государь.
— На Кавказе сложность в том, что Турция всегда готова обрушиться на наши границы первой. И Стамбул всегда ищет вооружённой поддержки против христианского мира среди кавказских народов.
— Что ж делать, это были и есть реалии всех русско-турецких войн. Последняя была не исключением.
— То-то и оно. В окружном штабе у вас, Николай Николаевич, работы будет очень много. Округ приказали готовить к возможной войне с Турцией.
— Да, ваше превосходительство, мне об этом известно.
— Тогда принимайте управление штабом. Но одновременно вам придётся начальствовать и над всем Кавказским военным округом. Что делать — ведь мне уже семьдесят четыре года: время берёт своё, не те уже стали силы, Николай Николаевич. Так что не обессудьте: не вы мне, а я вам помощник.
— Что вы, Илларион Иванович. Я надеюсь, что вы во мне найдёте должного исполнителя вашей воли.
— Берите в свои руки все бразды военного правления на Кавказе, Николай Николаевич, и, как говорится, с Богом...
Действительно, престарелый генерал Воронцов-Дашков постепенно переложил на плечи своего начальника штаба все заботы о войсках Кавказского военного округа. Юденич быстро освоился на новом месте, встретив взаимопонимание со стороны своих ближайших помощников по штабной работе.
Прежде всего Николай Николаевич постарался найти полное взаимопонимание с генералом от инфантерии Александром Захарьевичем Мышлаевским. Тот бы старым опытным генштабистом, назначенным помощником по военной части наместника Его Величества на Кавказе. Мышлаевский, человек высокой культуры и образованности, скоро увидел в новом начальнике окружного штаба своего единомышленника в кавказских делах и заботах. Они сдружились и самым добрым словом отзывались друг о друге до конца жизни.
Мышлаевскому, например, нравилось то, что генерал-лейтенант Юденич был из числа старых военных руководителей. Александру Захарьевичу импонировало, что его соратник интересовался, помимо служебных дел, ещё и обстановкой в регионе, где квартировали подчинённые ему войска. Кавказ всегда отличался сложностью обстановки, и начальнику штаба расположенного там военного округа приходилось заниматься ещё и дипломатической деятельностью.
Об этом у Юденича состоялся разговор с Воронцовым-Дашковым и Мышлаевским:
— Получено шифрованное письмо из Генерального штаба. По данным наших военных агентов в посольствах Турция активизирует свою антироссийскую деятельность в Персии и даже в Афганистане.
— Ваше превосходительство, об этом сообщают и начальники отрядов пограничной стражи. Они весьма осведомлены о том, что происходит за кордоном, в приграничье от Батума до Александрополя.
— Вот видите, господа, информация из Генерального штаба подтверждается на месте, у нас.
— Александр Захарьевич, надо запросить Министерство иностранных дел с просьбой присылать в Тифлис копии донесений военных агентов. Ситуацию мы должны прогнозировать на месте.
— Слушаюсь, ваше превосходительство.
— А вы, Николай Николаевич, как начальник окружного штаба, напрямую займитесь турецкими делами.
— Считайте, что ваше пожелание уже исполнено. Ещё вчера, как можно пошутить...
— Вместе с тем не забывайте о Персии, хоть она от нас и лежит за Каспием. Всё равно присматривайте за ней.
— Илларион Иванович, оперативный отдел штаба округа какую работу уже ведёт, смею вам доложить.
— Не забывайте, что в Генеральном штабе Турции полным-полно германских старших офицеров. Занимают не только места советников, но и командные должности. Есть и генералы с боевым опытом, для нас это опасные противники.
— Игра против нас уже идёт, ваше превосходительство. Но и мы не лыком шиты.
— Хорошо, если окружной начальник штаба так уверен в себе. Время, а может быть, и война покажет, кто кого переиграл.
— Думается, что нам ждать недолго...
Нагрузка на начальника штаба Кавказского военного округа нарастала буквально с каждым месяцем. Среди прочих обязанностей на генерал-лейтенанта Воронцовым-Дашковым и Генеральным штабом возлагалось непосредственное участие в работе военно-дипломатических миссий. В центре внимания Юденича, естественно, прежде всего находились сопредельные с Россией государства — Турция и Персия (Иран). Приходилось заниматься, но в гораздо меньшей степени, и Афганистаном.
Ещё в августе 1911 года в Санкт-Петербурге было подписано русско-германское соглашение по иранским делам. Оно частично смягчило возникшее в те годы острое противоречие государственных интересов Германии и России, оттянуло на несколько лет развязывание вооружённого конфликта между сторонами.
Волей дипломатических коллизий Тифлис оказался одним из объектов, с которым связывалось возрастание международного напряжения на Ближнем Востоке. Причиной стали серьёзные разногласия между Лондоном и Санкт-Петербургом. Известный британский дипломат Грей так высказался по этому поводу:
«...В отношении Персии мы хотим получить практически всю нейтральную зону и не можем ничего уступить там России; в отношении Афганистана мы не можем сделать каких-либо уступок России, так как мы не в состоянии получить согласия эмира; в отношении Тибета изменение, которого мы добиваемся и на которое необходимо согласие России, очень незначительно, и мы не можем ничего дать взамен. Таким образом, по всей линии мы хотим что-либо получить и не можем ничего дать. Вот почему трудно найти путь к совершению выгодной сделки».
В начале следующего года возникли серьёзные разногласия между Россией и Великобританией по поводу Персии. Причиной их стало назначение американца Моргана Шустера главным финансовым советником иранского правительства. Это было прямым ущербом российским интересам в Тегеране.