Явившись в Штаб округа, Деникин получил назначение на должность начальника Штаба 3-й Заамурской пограничной бригады, но, несмотря на то, что это было значительным повышением по службе (как правило, такую должность занимали в чине полковника), Антон Иванович искал любую возможность попасть на фронт: задачи Пограничной стражи были ограничены лишь охраной железных дорог.

28 марта 1904 года Деникин был произведен в подполковники, а в октябре представился и случай принять участие в боевых действиях. Деникину предложили занять место раненого начальника Штаба Забайкальской казачьей дивизии. Дивизией командовал генерал П. К. фон Ренненкампф, о котором шла солдатская молва как о храбром и боевом военачальнике.

19 ноября в столкновении с японцами у деревни Уйцзыюй генерал Ренненкампф поздравил своего нового начальника Штаба с боевым крещением, а спустя пять дней Деникин возглавит авангард в Цинхеченском бою. Это будет его первый опыт самостоятельного командования отрядом, состоявшим из полутора батальонов, четырех сотен казаков и горной батареи. В течение пяти дней Деникин отбивал атаки японцев, поднимая иногда своих солдат в штыки. В историю Русско-Японской войны впоследствии войдут названия сопок, где особенно ярко проявился русский героизм. Одна из них будет названа Деникинской.

В Мукденском сражении подполковник Деникин принял участие в должности начальника Штаба Урало-Забайкальской казачьей дивизии. Русские войска сражение проиграли, но даже в условиях командной неразберихи сохранили организацию и моральную стойкость.

Урало-Забайкальская казачья дивизия входила в состав большого конного отряда генерала П. И. Мищенко, особенно прославившегося в известном набеге в тыл японцев и в деле у Санвайзы 20 и 21 мая. В отряде Мищенко Деникин принял участие и в последнем бою Русско-Японской войны под Санвайзой 1 июля 1905 года, отличившись при штурме опорного пункта неприятельской позиции и разгроме батальона японской пехоты. За боевые отличия в делах с японцами Антон Иванович был награжден орденами Святой Анны III-й степени с мечами и бантом, Святого Станислава II-й степени с мечами, Святой Анны II-й степени с мечами и, наконец, чином полковника. Высокой похвалой прозвучали и слова генерал-адъютанта Мищенко в приказе по Сводному кавалерийскому корпусу: «По справедливости я должен признать деятельность этого достойного офицера Генерального штаба высоко полезной как в отношении внутреннего быта частей дивизии, так и в особенности боевой службы, которая была очень трудной и ответственной. Все это время боевой жизни и службы с дивизией полковник Деникин проявлял выдающуюся энергию, работоспособность, усердие, правильное понимание и любовь к военному делу. Расставаясь ныне с полковником Деникиным, считаю своим долгом от лица службы искренне поблагодарить его и пожелать ему светлого будущего».

По окончании войны Антон Иванович служил в Штабе II-го кавалерийского корпуса в Варшаве. Это было временным назначением, которое, впрочем, длилось ровно год. Столь длительному ожиданию вакансии было объяснение. В Главном управлении Генерального Штаба, которое ведало назначениями генштабистов, были вынуждены вспомнить опального капитана Деникина в связи с его новым проявлением характера: покидая 3 декабря 1905 года Дальний Восток, он направил начальнику Штаба при Главнокомандующем сухопутными и морскими силами на Дальнем Востоке письмо, где после перечисления сражений, в которых он принял участие, говорилось:

«…Генерал-адъютант Мищенко пять раз входил с представлением о награждении меня, и все представления в высших инстанциях были отклонены – факт сам по себе ничтожный, если бы не имел характера полного и оскорбительного отрицания моей боевой работы. Я далек от мысли приписывать это Главнокомандующему или командующему армией. Исключительно высокое положение этих лиц гарантирует полное их беспристрастие, и, не зная меня лично, они, конечно, не имели повода не доверять оценке генералов Ренненкампфа и Мищенко, под руководством которых я работал. Наконец, щедрость Главнокомандующего в деле награждения, в особенности в последнее время, беспримерна.