Два года спустя Каледин получил под командование 12-ю кавалерийскую дивизию, дислоцировавшуюся в Проскурове и входившую в состав 12-го армейского корпуса, командиром которого вскоре был назначен генерал от кавалерии А. А. Брусилов. Так впервые сошлись служебные пути двух военачальников, имена которых затем неоднократно будут стоять рядом в победных реляциях в годы Первой мировой войны.
Брусилов, долгие годы возглавлявший Офицерскую кавалерийскую школу, а затем командовавший гвардейской кавалерийской дивизией, считался большим специалистом этого рода войск. Вполне понятно, что он проявлял повышенный интерес к соединению Каледина и несколько раз наезжал для его проверки из Винницы, где находился штаб корпуса.
Известие о вступлении России в войну с Австро-Венгрией, а затем и с Германией не было для Каледина неожиданным. Через прессу он знал об убийстве в Сараево и реакции на это различных европейских государств. Документы, поступавшие из штабов Киевского военного округа и корпуса, требовали скорейшей подготовки русских войск к военным действиям. О приготовлениях противоположной стороны ежедневно доносили из охранявших границу подразделений корпуса пограничной стражи. Все это не оставляло сомнений, что не сегодня, так завтра поступит приказ о мобилизации в России и начнется война, в которую 12-й кавалерийской дивизии придется вступить одной из первых. Поэтому Алексей Максимович делал все возможное, чтобы подчиненные ему войска были готовы к серьезному испытанию.
Обстановка тем временем становилась все тревожнее. Тем неожиданней для него стал приказ о назначении Брусилова командующим 8-й армией, а командиром 12 армейского корпуса – генерал-лейтенанта Л. В. Леша.
Соединение генерала Каледина приняло боевое крещение 9 (22) августа в бою под Тарнополем. В конном строю дивизия атаковала кавалерийские части противника и, нанеся им поражение, открыла корпусу путь в глубь территории Австро-Венгрии. По докладу, представленному командиром корпуса Брусилову, в этом бою Алексей Максимович «показал себя образцовым начальником и бесконечно храбрым человеком».
Наступление 8-й армии развивалось успешно. Через шесть дней, в результате непрерывного марша, ее соединения вышли на подступы к старинному городу Галичу и завязали бои на его дальних подступах. Однако обстановка, сложившаяся в это время севернее в полосе 3-й армии, потребовала от генерала Брусилова изменить направление главного удара. Оставив незначительный заслон у Галича, он направил остальные соединения на Львов, охватывая город с юго-востока.
Впереди 8-й армии действовала кавалерия, в том числе и дивизия Каледина. 16 (29) августа ей одной из первых довелось принять на себя встречный удар противника на реке Гнилая Липа. В этом бою Каледин отличился настолько, что был один из первых генералов русской армии с начала войны награжден орденом Святого Георгия 4-й степени. В наградном листе было отмечено, что «в сражении при Гнилой Липе 16 августа 1914 года, получив сведения о движении противника по лесному пространству к переправам через реку Гнилую Липу у сел Руды и Клещевки, Алексей Каледин по своей инициативе, спешив всю дивизию и заняв своей артиллерией позиции, выдержал очень упорный бой и, несмотря на большие потери, предотвратил прорыв значительно превосходящих его силы противника в промежуток между двумя дивизиями и удержался до подхода к утру 17 августа пехотного полка».
После успешного завершения боев на Гнилой Липе русские войска устремились по направлению к Львову. Темпы наступления были столь высокие, что австро-венгерское командование, опасаясь окружения своих войск, решило оставить этот город без боя.
Разведка 12-й кавалерийской дивизии одной из первых установила начало отхода противника. Узнав об этом, Алексей Максимович приказал от каждого из полков выделить авангарды, которые должны были ночным форсированным маршем настичь неприятельские части сразу же за Львовом. И лишь незначительные силы были направлены непосредственно в город, чтобы убедиться в отсутствии в нем вражеских войск. По докладам командиров этих подразделений Каледин подал рапорт Брусилову, затем немедленно переправленный – в штаб Юго-Западного фронта. Рапорт гласил: «Сегодня, 21 августа, в 11 часов утра разъезды 12-й дивизии вошли в оставленный неприятелем город Львов. Встречены жителями очень приветливо».
Весть о падении Львова была радостно встречена в Ставке Верховного главнокомандующего и в Петрограде. Однако лавры этой победы достались не Брусилову, а командующему 3-й армией генералу Рузскому. Обиженный этим Брусилов все свое внимание сосредоточил на левом фланге армии, где соединения 24 корпуса 22 августа захватили город Галич. Но радость этой победы, доставившей командарму столь желанный орден Св. Георгия 4-й степени, оказалась преждевременной.