На период подготовки к операции Юденич перенес свой полевой штаб в селение Караурган, поближе к войскам. Подготовка велась в строжайшей тайне: перемещение войск совершалось только по ночам, а днем войска демонстративно «уходили» с позиций, создавая тем самым у турок впечатление, что численность армии сокращается. Интенданты, получая новые приказы, пребывали в уверенности, что армия просто тщательно готовится к зимовке (среди экипировки бойцов Отдельной Кавказской армии были валенки, полушубки, стеганые ватные шаровары, варежки и даже темные очки, защищавшие от слепящего горного солнца). В этом же были уверены работники всех семнадцати армейских метеостанций, ежедневно анализировавших состояние погоды в горах. Незадолго до Рождества в Тифлис из разных частей было откомандировано множество офицеров и солдат для закупки рождественских елок и подарков. Более того, в армии специально распространялся вполне правдоподобный слух о предполагаемой весной экспедиции в Персию… Словом, в Отдельной Кавказской армии только несколько человек знали о том, что готовится крупная наступательная операция. Первая в истории русских вооруженных сил кампания по дезинформации противника удалась блестяще…
Вечером 22 декабря 1915 года Юденич поездом выехал из Карса в Тифлис на встречу с великим князем Николаем Николаевичем. Выслушав доклад генерала, наместник, поколебавшись, дал согласие на проведение операции.
Командиры корпусов узнали о том, что именно им предстоит, за сутки до начала наступления, причем каждый из них был уверен, что именно он нанесет противнику решающий удар. 29 декабря 1915 года после мощной артподготовки пошел в наступление 2-й Туркестанский армейский корпус (командующий — генерал-лейтенант М.А. Пржевальский), на следующий день его поддержал 1-й Кавказский армейский корпус (командующий — генерал от инфантерии П.П. Калитин).
Турки совершенно не ожидали наступления — об этом можно судить хотя бы по тому, что командующий их 3-й армией Махмуд-Камиль-паша находился в отпуске в Константинополе. Однако противник быстро оправился и оказал русским войскам ожесточенное сопротивление, особенно 29 декабря у горы Гейдаг и 31 декабря на Азанкейской позиции. Азанкейское плато было кратчайшим путем к Эрзеруму, поэтому неудивительно, что именно здесь турки сражались особенно отчаянно и именно сюда направлялись все резервы. Ночью одетые в белые маскхалаты бойцы 153-го пехотного Бакинского полка быстро захватили первую линию обороны врага, но затем натолкнулись на сильное сопротивление и весь следующий день вели на плато тяжелейший бой, потеряв больше двух тысяч человек убитыми и ранеными, но не отступив при этом ни на шаг. Сражавшийся левее Бакинского 154-й пехотный Дербентский полк лишился всех своих штаб-офицеров и его повел на приступ позиции протоиерей отец Павел (Смирнов). После двух неудачных атак он с крестом в руках возглавил батальон полка и взял сильное турецкое укрепление у села Тарходжа, причем был настолько тяжело ранен, что священнику пришлось ампутировать ногу. За этот подвиг отец Павел 7 ноября 1916 года был награжден орденом Святого Георгия 4-й степени.
Ярость боев на Азанкейском плато заставила турок поверить в то, что главный удар наносится русскими именно здесь. Между тем Юденич, пристально следивший за ходом сражения, бросил в прорыв ударную группу генерал-лейтенанта Н.М. Воробьева — 4-ю Кавказскую стрелковую дивизию, усиленную 261-м пехотным Ахульгинским, 262-м пехотным Грозненским и 263-м пехотным Гунибским полками. В метельную ночь на новый, 1916 год эта группа прорвала фронт турок в труднодоступном районе Меслагат, где противник не ожидал атак, и вышла во фланг и тыл 11-му турецкому корпусу. Известие об этом вызвало в рядах турок панику (они вообразили, что в прорыв пошли несколько свежих русских корпусов), и в ночь на 4 января турецкие 9-й и 11-й корпуса обратились в бегство. 6 января с ходу была взята крепость Гасан-кала, куда Юденич немедленно перенес свой полевой штаб. Потери турецких войск составили 25 тысяч человек убитыми и ранеными и 7 тысяч пленными, русских — 20 тысяч убитыми и ранеными. 17 января 1916 года по итогам операции Н.Н. Юденич был награжден орденом Святого Александра Невского с мечами.
Но окончательная цель сражения достигнута еще не была. Азанкейская позиция открыла путь к Эрзеруму — «сердцу» турецкой армии, но отдавать его без сопротивления противник, даже деморализованный недавним поражением, не собирался. Учитывая высочайший моральный дух своих войск, воодушевленных победой, и хаос в рядах полуразбитой 3-й турецкой армии, Н.Н. Юденич принял решение немедленно штурмовать крепость и тем самым добить турецкие вооруженные силы на Кавказе.