Не обошла стороной война и семью Юденича. С первых же месяцев после отъезда мужа на фронт Александра Николаевна все силы отдавала организации особого лазарета, оборудованного в соответствии с последними достижениями хирургической науки. Она практически «с нуля» создала лечебное заведение, где тысячи раненых находили внимание и уход. Ею же была организована помощь женам мобилизованных солдат и офицеров. Создавались мастерские по пошиву обмундирования, изготовлению военного снаряжения. При мастерских были открыты ясли для детей работниц.
Следующим этапом полководческой карьеры Юденича стал штурм крепости Эрзерум. С началом нового, 1916 года Кавказская армия вплотную подошла к казавшейся неприступной твердыне. Стратегически взятие Эрзерума означало примерно то же самое, что и взятие Перемышля на Юго-Западном фронте: нельзя было продолжать наступление, выходить на равнины Анатолии, имея в тылу мощную крепость с многочисленным гарнизоном. Юденич, снова проявляя нестандартность оперативного мышления, решает взять крепость без длительной осады, что называется, с ходу. Однако против проведения операции выступили как Верховный Главнокомандующий, Император Николай II, так и сменивший Воронцова-Дашкова на посту Главнокомандующего Кавказским фронтом Великий Князь Николай Николаевич.
Генерал Н. Н. Юденич (х) со штабом на стене Эрзерумской крепости. 1916
Окруженный горами, хорошо защищенный артиллерией, Эрзерум представлял собой серьезный укрепленный район. Положение осложнялось еще и тем, что штурм происходил зимой, в условиях обледенения немногочисленных дорог, засыпанных снегом горных перевалов. Но ничто уже не могло заставить Юденича отказаться от принятого, стратегически рассчитанного и оправданного (а в этом у него не возникало сомнений) решения. Определенную роль сыграли дошедшие до него известия о том, что после поражения десанта союзников в Галлиполийской операции освободившиеся турецкие войска начали перебрасываться на Кавказ.
Хорошую оценку этому решению Юденича дал генерал Б. А. Штейфон, участник Эрзерумской операции: «В действительности каждый смелый маневр генерала Юденича являлся следствием глубоко продуманной и совершенно точно угаданной обстановки. И, главным образом, духовной обстановки. Риск генерала Юденича – это смелость творческой фантазии, та смелость, какая присуща только большим полководцам». Ему вторил генерал-квартирмейстер Кавказской армии генерал Е. В. Масловский: «…Генерал Юденич обладал необычайным гражданским мужеством, хладнокровием в самые тяжелые минуты и решительностью. Он всегда находил в себе мужество принять нужное решение, беря на себя и всю ответственность за него, как то было в Сарыкамышских боях и при штурме Эрзерума. Обладал несокрушимой волей. Решительностью победить во что бы то ни стало, волей к победе весь проникнут был генерал Юденич, и эта его воля в соединении со свойствами его ума и характера являли в нем истинные черты полководца».
Помимо чисто стратегических расчетов Юденич прекрасно чувствовал и моральную обстановку, сложившуюся в те дни на Кавказском фронте. А она была еще весьма далека от того хаоса и развала, которые охватят полки и дивизии всего лишь через год. Не испытавшая пагубного влияния «окопного сидения» Кавказская армия готова была идти вперед. У войск был порыв, и именно его чувствовал командующий, когда принимал решение об атаке неприступного Эрзерума.
Взяв на себя всю ответственность за последствия операции, Юденич начал штурм. В течение двадцати дней прошла перегруппировка сил. Для взятия крепости было сосредоточено две трети личного состава Кавказской армии и бо́льшая часть артиллерии. Подготовка велась в обстановке повышенной секретности. 29 января 1916 года после мощной артиллерийской подготовки, ночью, в сильную метель и мороз штурмовые отряды пошли на приступ. Юденич приказал вести атаку круглые сутки, без перерыва. Сам он с небольшим конвоем и штабными офицерами разместился прямо на передовой. Несмотря на значительные потери штурмовавших, отчаянное сопротивление турецкого гарнизона было сломлено, и уже к утру 3 февраля Эрзерум выкинул белый флаг.
Великий Князь Николай Николаевич, поздравляя войска с победой, снял перед строем папаху и, повернувшись к Юденичу, низко поклонился ему, после чего провозгласил, обратившись к войскам: «Герою Эрзерума, генералу Юденичу ура». За эту беспримерную в истории русского военного искусства Великой войны операцию Юденич был награжден орденом Святого Георгия II-й степени (один из редких случаев в последние десятилетия Российской Империи).