Рана заживала довольно быстро. Этому во многом способствовал приезд жены, которая окружила мужа нежной заботой и вниманием. Так и не долечившись до конца, в середине марта Алексей Максимович вернулся в свою дивизию, которая в это время вела тяжелые бои на Ужокском направлении в Карпатах.
Каледин быстро разобрался с обстановкой и решительно отказался от фронтальных атак противника в конном строю, которыми все еще увлекалось русское командование, в том числе и Брусилов. Он потребовал наступать исключительно в пешем порядке, максимально используя складки местности для выхода на фланги и в тыл австрийских войск, занимавших господствующие высоты. С целью достижения внезапности в ряде случаев стали практиковаться ночные действия.
Изменения в тактике дали положительные результаты. Начиная с 24 марта в сводках штаба Верховного главнокомандующего постоянно отмечаются успешные действия русских войск на Ужокском направлении. Так, сводка за 30 марта гласила: «На Ужокском направлении после упорного боя мы овладели несколькими высотами, причем захвачено 1000 пленных с 22 офицерами и 4 пулемета». «Упорным боем в районе Ужокского перевала, который продолжает удерживать неприятель, мы несколько продвинулись вперед. Нами захвачено 3 орудия и до 700 пленных» – отмечалось на следующий день. Значительная часть успеха была обеспечена действиями соединения генерала Каледина. По итогам мартовских боев он был награжден орденом Св. Владимира 2-й степени с мечами.
19 апреля (2 мая), перегруппировав австро-венгерские войска и значительно усилив их германскими соединениями, противник начал крупномасштабное наступление в Греции, получившее название Горлицкого прорыва. Армии Брусилова пришлось отходить к Перемышлю, ведя непрерывные арьергардные бои. Основная их тяжесть легла на кавалерию, в том числе и на дивизию Каледина.
Алексей Максимович в условиях значительного превосходства противника в силах и средствах, и прежде всего в артиллерии, противопоставил врагу активную маневренную оборону на широком фронте. Расчленив дивизию на полки и эскадроны, он умело сочетал удержание нескольких последовательных рубежей с засадами и короткими контратаками. При этом быстрая смена одних действий другими, стремительный маневр войск в широкой полосе и ночные рейды небольших отрядов добровольцев во вражеский тыл держали противника в постоянном напряжении, существенно сковывали его наступление. Благодаря этому отход 8-й армии к Перемышлю прошел организованно. Были эвакуированы все раненые, больные и вывезены ценные грузы. За умелое руководство соединением во время отхода 1 мая 1915 года Каледин награжден орденом Белого Орла с мечами.
После двухнедельной упорной обороны 21 мая русские войска оставили Перемышль. 9 июня практически без боя противнику сдан Львов. 8-я армия поспешно перешла к обороне по восточному берегу Западного Буга.
Брусилов тяжело переживал неудачи. 17 июня он собрал на совещание командиров корпусов и заслушал их предложения по плану дальнейших действий. На следующий день командарм пригласил к себе Каледина, который всего за несколько часов до этого с последними частями арьергарда перешел через Западный Буг и лучше других владел обстановкой. Доклад продолжался более двух часов и вскоре вышел за пределы компетенции командира дивизии. Алексей Максимович предложил Брусилову интересный, хотя и несколько рискованный вариант действий, к которому тот отнесся с большим интересом.
18 июня Каледин неожиданно для себя был назначен командиром 41-го армейского корпуса, сменив раненого генерала Хана Нахичеванского. В следующем месяце он был утвержден командиром ранее уже предназначавшегося ему 12-го армейского корпуса.
В сентябре 1915 года австро-венгерское командование попыталось прорвать оборону 8-й армии на Луцком направлении. Наступление врага было сорвано умелой обороной корпуса Каледина, за что Алексей Максимович получил орден Святого Георгия 3-й степени.
В середине марта 1916 года генерал А. А. Брусилов стал командующим войсками Юго-Западного фронта. На пост командующего 8-й армией вместо себя он просил Ставку назначить начальника штаба армии генерала В. Н. Клембовского. На эту просьбу начальник штаба Ставки генерал М. В. Алексеев ответил, что император Клембовского знает очень плохо и что хотя Брусилов и не стеснен в выборе своего преемника, но ему настоятельно рекомендуется выдвинуть на этот пост генерала Каледина, кандидатурой которого «государь был бы доволен».