Начальником Главного Управления военно-учебных заведений в то время был Великий Князь Константин Константинович, пользовавшийся большой популярностью у кадет и юнкеров, при посещении своих корпусов и училищ часто устраивавших ему торжественные встречи и буквально носивших его на руках. Именно на него Кутепов произвел столь благоприятное впечатление на смотру 11 июля 1903 года, что тут же, на плацу, был произведен «за отличное командование своей ротой» сразу в фельдфебели, минуя звание старшего портупей-юнкера, - как говаривал позднее он сам, «по-екатеринински». Конечно, это укрепляло преклонение перед монархией в целом и Императорской Фамилией как ее зримым воплощением. Помимо успехов в теоретических и строевых занятиях, Кутепов прославился и как лучший фехтовальщик училища, что подтверждает полученный им 6 июля 1904 года приз за бой на эспадронах. При выпуске фельдфебель первым выбирал вакансии и мог выйти в самые завидные полки. Но уже шла Русско-Японская война, и Кутепов стремился в Действующую Армию. Произведенный в подпоручики, 9 августа 1904 года он отбыл на Дальний Восток в 85-й пехотный Выборгский Его Императорского и Королевского Величества Императора Германского Короля Прусского Вильгельма II полк.

Назначенный помощником начальника команды конных охотников (разведчиков), молодой подпоручик с первых дней службы проявил настойчивость, выдержку, смекалку и храбрость. По два-три, а то и пять раз за день он водил своих людей в разведку, причем благодаря умелому командиру они почти не несли потерь. Как-то Кутепов едва не был зарублен хунхузом, но выручило искусное владение шашкой; однако первое убийство, да еще холодным оружием в ближнем бою, внушило отвращение и долго не могло забыться. В другой раз была рассеяна японская застава (более 70 человек), а ее оружие, включая пулеметы, стало трофеями охотников. Самым замечательным в этом деле стало то, что подпоручик не только не был награжден (орден Святого Георгия IV-й степени получил начальник команды, в вылазке не участвовавший), но и фактически умолчал о своей роли; только после войны один из офицеров случайно узнал от солдат истину. Редкое свободное время Кутепов также посвящал службе. «Скромного, всегда по форме одетого подпоручика Кутепова трудно было уговорить выпить одну-две рюмки водки, а о том, чтобы он играл в карты, - никто и не слыхал», — с некоторым недоумением вспоминал однополчанин.

Во время Мукденского сражения Кутепов отличился в деле у Кудяза 25 февраля 1905 года, за что 5 мая получил орден Святого Станислава III-й степени с мечами и бантом; 24 июля он был отмечен второй наградой — орденом Святой Анны IV-й степени с надписью «За храбрость». Когда же в полку побывал германский Принц, он заметил подтянутого офицера и, выслушав его доклад об одной из разведок, пожелал наградить его от имени Августейшего Шефа полка. В результате 16 января 1906 года пришло разрешение «принять и носить пожалованный Императором Вильгельмом II прусский орден Короны 4-й ст[епени] с мечами на черной ленте с белыми полосами по краю».

Между тем война закончилась, и еще 2 октября 1905 года Кутепов, не получивший на ней и царапины, был откомандирован в Новгород, в 85-й пехотный запасный батальон, для обучения молодых солдат. Легко представить его горечь от поражения в войне и особенно - от столкновения с охватывавшей страну революционной стихией. Следуя с эшелоном через всю Россию, он поражался и негодовал, но уж никак не терялся: в Иркутске, где произошла было задержка, подпоручик арестовал местный комитет и добился отправки эшелона дальше. Прибыв в Новгород, Кутепов приступил к исполнению своих служебных обязанностей. А награды продолжали догонять его. 22 мая 1906 года из рук самого Императора Николая II он получил орден Святого Равноапостольного Князя Владимира IV-й степени с мечами и бантом, а вскоре был произведен в поручики.

Революция же продолжалась, и именно она стала косвенной причиной дальнейшего поворота в судьбе Александра Павловича. В июне 1906 года произошли волнения в старейшем, безукоризненном полку Императорской Гвардии - Лейб-Гвардии Преображенском. Суть событий была такова. Нижние чины 1-го батальона (командиром которого считался сам Император) образовали толпу во дворе казарм, что-то обсуждали и, вопреки приказанию, не расходились. Дежурный офицер вместо мер принуждения доложил по команде; когда известие дошло до Командующего войсками Гвардии, Великого Князя Николая Николаевича (Младшего), тот, нарушая уставы, велел замять дело. Опрос солдат о жалобах, произведенный крайне искаженно, привел к подаче ими письменного коллективного заявления (само по себе деяние недопустимое), в котором явно звучали политические мотивы - например, требование «свободы печати». Правда, при разбирательстве выяснилось полное непонимание солдатами смысла собственной петиции (под «печатью» они понимали полковую круглую печать и т. д.), что говорило о внушении требований извне, то есть об агитации. Николай Николаевич, видя тщетность попыток скрыть происшествие, заявил уже о «бунте». Агитаторов нашли и наказали, но немилость пала и на весь батальон, который раскассировали полностью, включая и офицеров. Были спороты и Шефские вензеля с погон. Большинство солдат, не участвовавших в волнениях, плакали и умоляли о прощении, что никак не вяжется с образами «бунтовщиков».

Многие сочли огульное наказание слишком жестоким, но в действительности было просто невозможно выявить всех смутьянов, что давало опасность сохранения их в Гвардии; требовалось примерное наказание, - кстати, оказавшееся весьма мягким. А во вновь сформированный 1-й батальон подбирались самые отличившиеся и благонадежные офицеры из числа участников последней кампании. 13 декабря 1906 года прикомандированным Лейб Гвардии к Преображенскому полку оказался и поручик Кутепов, причем «за свои боевые отличия... в том же чине и с тем же старшинством». При учете преимущества офицеров Гвардии перед армейскими это фактически означало производство. 12 июля 1907 года Кутепов был окончательно принят в полк и приступил к временному исполнению должности начальника пулеметной команды.

Через некоторое время он стал помощником начальника полковой учебной команды, что означало наибольшее по сравнению с другими офицерами приближение к роли воспитателя солдат. Кутеповские методы были просты и действенны. Вначале тщательно, доходчиво и терпеливо он объяснял и внушал требования, затем указывал на нарушения, а потом, если они продолжались, беспощадно налагал дисциплинарные взыскания. Но при этом никогда не позволял себе рукоприкладства и добивался, чтобы даже старые унтер-офицеры вели себя так же. Кутепов считал звание солдата почетным и просто не мог унижать его. Другой его особенностью являлось полное и нарочитое игнорирование традиционной разницы в отношении к солдатам и вольноопределяющимся. Кутепов был убежден, что настоящие воины должны соответствовать равным требованиям без каких бы то ни было поблажек отдельным их категориям. Проштрафившихся не бранил, не кричал на них, а иногда даже не подвергал взысканиям, ибо гораздо действеннее бывала укоризненно брошенная вполголоса его любимая присказка: «Эх, Федора Ивановна!» В праздничные и воскресные дни Кутепов часто водил молодых солдат в музеи, театры, галереи и рассказывал об истории и искусстве. Этим опровергается поздний запальчивый отзыв о нем генерала Я. А. Слащова как о человеке, «не бравшем с момента производства книги в руки». Нижние чины видели и строгость, и справедливость Кутепова и прозвали его «правильный человек».

В то же время и после перехода в Гвардию Кутепов продолжал оставаться тем, кем был до этого, - заурядным в хорошем смысле слова служакой, не вынашивающим честолюбивых планов. Именно такие офицеры старательно тянули лямку, являясь прекрасными исполнителями приказов начальства и идеальными командирами своих рот и батальонов. Александр Павлович ясно осознавал, что он — армейский провинциал, совсем не светский и не знатный — воспринимался многими кадровыми Лейб-Гвардейцами, при всей доброжелательности, как чужак, и что военно-придворная карьера для него закрыта. Не стремился он и в Академию Генерального Штаба, чувствуя призвание к строевой службе. Возможно, впоследствии Кутепов планировал перевестись в армейский полк, используя преимущество в чинах.