Следующие долгие пятнадцать лет Николай Николаевич Юденич проходит службу в штабе хорошо знакомого ему Туркестанского военного округа. Он хорошо продвигается по служебной лестнице — в 1892 году получает звание подполковника, а еще через четыре года становится полковником. В Туркестане он последовательно назначался на должности командира батальона пехоты и начальника штаба Туркестанской стрелковой бригады.
Для руководства военного ведомства Российской империи примерная служба полковника Н. Н. Юденича не осталась незамеченной. Он получает назначение в приграничный Виленский военный округ на должность командира 18-го стрелкового полка. Послужной список полкового командира свидетельствует о том, что командование отдельной воинской частью для Юденича проходило достаточно успешно, но и не без трудностей. На проходивших учениях его стрелки демонстрировали хорошую выучку, а роты имели устроенный быт.
С началом русско-японской войны 1904—1905 годов 18-й стрелковый полк вошел в состав 5-й стрелковой бригады 6-й Восточно-Сибирской дивизии. Путь на поля Маньчжурии лежал длинный и долгий — почти через всю Россию, сперва по железной, перегруженной воинскими эшелонами дороге, а затем и своим ходом.
К тому времени полковник Н. Н. Юденич был уже степенным человеком, нашедшим свое семейное счастье. Он женился на Александре Николаевне, урожденной Жемчуговой. Брак армейского офицера с девушкой из родовитой дворянской семьи оказался крепким, и супругов отличало взаимопонимание и любовь.
Прибыв в Маньчжурию, стрелковый полк Юденича скоро оказался в самом пекле боевых действий. Бездарность командования русской армией стала притчей во языцех. Главнокомандующий генерал Куропаткин проигрывал одно сражение за другим, порой только из желания отступить еще дальше к российской границе. Восточно-сибирские полки и дивизии несли неоправданно большие потери в людях.
Самой крупной операцией в ходе русско-японской войны для полковника Н. Н. Юденича стало участие со своим полком в Мукденском сражении, которое проходило с 6 по 25: февраля 1905 года. 18-й стрелковый полк оказался в числе тех правофланговых русских войск, на которые обрушился обходной удар 3-й японской армии, стремившейся выйти в тыл противнику севернее города Мукдена и перерезать там железную дорогу.
Ранним утром 19 февраля 5-я и 8-я японские дивизии 3-й японской армии, которой командовал генерал М. Ноги, перешла в наступление на участке Мадяпу, Сатхоза, Янсынтунь. Последний населенный пункт обороняли стрелковые бригады 6-й Восточно-Сибирской дивизии. Сибирской она была только по названию, так как предназначалась для Сибири, а формировалась в европейских губерниях страны.
Бойцы полковника Н. Н. Юденича занимали позиции на окраине большого китайского селения Янсынтунь. Стрелки укрывались в наскоро вырытых неглубоких окопах среди полей чумизы и гаоляна. Японская артиллерия обстреливала русские позиции из своих батарей, подтянутых к передовой.
С восходом солнца японская пехота начала массированные атаки позиций полка Юденича. Лежа на мерзлой земле, под разрывами вражеской шрапнели, стрелки отбили несколько сильных неприятельских атак. Полковой командир демонстрировал «примерное», как тогда писалось в наградных представлениях, личное мужество и бесстрашие.
Только при получении приказа свыше 18-й стрелковый полк отошел с занимаемой позиции, уступив ее японцам. Генералу М. Ноги, одному из лучших полководцев императорской армии, в сражении под Мукденом так и не удалось совершить фланговый обхват русской армии — на пути атакующих японских дивизий встали полки сибирских стрелков. Многие прославили себя в тех жарких и кровопролитных боях на равнине к востоку от реки Ляохэ.
Российский историк-белоэмигрант А. А. Керсновский в «Истории русской армии», описывая Мукденское сражение, называет фамилии трех полковых командиров, составивших себе в февральские дни 1905 года блестящую репутацию. Это командир 18-го стрелкового — полковник Юденич, 1-го Сибирского — полковник Леш и 24-го Сибирского — полковник Лечицкий. Обращает на себя внимание то, что Николай Николаевич Юденич назван в этом коротком списке первым.
За отличие в сражении под Мукденом, проявленную стойкость и храбрость личный состав 18-го стрелкового полка высочайшим указом императора Николая II Романова был удостоен особого знака отличия с надписью «За Янсынтунь. Февраль 1905 года». Этот знак крепился на головных уборах нижних чинов — солдат и унтер-офицеров.
Полковой командир за бои под Мукденом на Янсынтуньской позиции удостоился высокой воинской награды, особо чтимой в русской армии на протяжении трех столетий. Полковник Николай Николаевич Юденич был награжден Золотым оружием — офицерской саблей с гравированной надписью «За храбрость». С этим наградным оружием он пройдет через две войны — первую мировую и гражданскую.