В Японской кампании Кутепов принял участие в качестве офицера полковой команды охотников, то есть разведчиков (с 9 мая 1905 года — помощник начальника команды). Знавший его в те годы офицер А. А. Шеин вспоминал Александра Павловича так: «В то время не было лысины и бороды, маленькие усы, вся фигура была более сухая, худощавая и юношески подтянутая, только глаза были те же, но в них было меньше грусти и часто вспыхивали искорки задора. <…> Два раза по приглашению А. П. я участвовал в его ночных экспедициях, предпринятых для разведки производимых японцами работ. Как правило, в ночь, предшествовавшую такой разведке целой командой, А. П. производил таковую сам с одним или двумя из своих охотников, тщательно подготовляя успех действий команды и часто рискуя собой лично, он старался довести до минимума риск в действиях своих подчиненных. Все его ночные разведки — а они происходили чуть ли не 2–3 раза в неделю, — носили отпечаток тщательной подготовки, продуманности, почему и потери всегда были очень незначительны». Запомнилось Шеину и то, что «скромного, всегда аккуратно и по форме одетого подпоручика Кутепова трудно было уговорить выпить одну-две рюмки водки, а о том, чтобы он играл в карты, — мне и слышать не приходилось».

Тяготы службы для Кутепова скрашивала дружба с однокашником по училищу — подпоручиком Максимом Эдуардовичем Леви. Они вместе ходили на боевые «дела», вместе отдыхали, устраивали «балы», на которых в качестве угощения выступали пирожки и пельмени. Но 20 февраля 1905 года командующий 8-й ротой подпоручик Леви был убит пулей в висок. Александр Павлович глубоко переживал гибель друга, после войны навестил его мать и, по-видимому, в чем-то считал себя ее сыном, так как переписывался с ней на протяжении четверти века, а она ласково называла его Шуриком.

Боевые заслуги подпоручика во время Русско-японской войны были отмечены несколькими наградами: орденами Святого Станислава 3-й степени с мечами и бантом (5 мая 1905 года), Святой Анны 4-й степени «За храбрость» (так называемое Анненское оружие, 14 июля 1905 года), Святого Владимира 4-й степени с мечами и бантом (22 мая 1906 года, его Кутепову вручал лично Николай II). Помимо русских наград, его мундир украсила и первая иностранная — прусский орден Короны 4-й степени с мечами на ленте Железного креста. Ее получение было связано с тем, что шефом 85-го пехотного Выборгского полка был император Германии и король Пруссии Вильгельм II.

После завершения кампании Кутепов был откомандирован в 85-й пехотный запасной батальон, стоявший в Новгороде. Но проехать в Центральную Россию оказалось не так-то легко: Сибирь была охвачена революционным движением, на станциях Иркутск, Верхнеудинск и Красноярск воинские эшелоны задерживались бастующими. Кутепов не раздумывал долго, во главе горсти преданных ему и присяге солдат он арестовал революционный комитет и добился отправки эшелонов. Звучит просто, но можно себе представить, сколько мужества и решимости потребовалось юному подпоручику, чтобы переломить ситуацию в свою пользу! Это был первый опыт борьбы Кутепова с революционной стихией, и опыт вполне успешный.

В декабре 1906 года в служебной судьбе Кутепова наступил важный перелом, повлиявший на всю его дальнейшую карьеру, — он получил перевод в лейб-гвардию, точнее, в лейб-гвардии Преображенский полк — старейший в русской армии.