Впрочем, в Забайкальи молодой офицер пробыл недолго: по истечении обязательного срока службы в строю, в 1886 году сотник Каледин поступает в Николаевскую Академию Генерального Штаба и оканчивает ее в 1889-м, по первому разряду и с производством «за отличные успехи в науках» в подъесаулы. Будучи причислен к Генеральному Штабу, а через семь месяцев и переведен в него, Каледин шесть лет служит в приграничном Варшавском военном округе, среди других вопросов занимаясь организацией укрепленных районов на случай будущей войны. Современник рассказывал о памятном брелоке, подаренном Алексею Максимовичу сослуживцами – «на синей эмали, окаймленной золотым ободком, маленькие золотые звездочки»: «синее поле – укрепленный район, звездочки – крепости».
В Варшаве капитан Каледин встретил женщину, которая стала его женой, любовь которой, верная и преданная, доходящая до преклонения, озаряла его жизнь до самых последних дней, – Марию-Луизу Оллендорф, урожденную Ионер (она происходила из одного из франкоговорящих кантонов Швейцарии). Свадебным же путешествием для Алексея Максимовича и Марии Петровны (так будут называть ее, хотя в Православие она не перешла) станет дорога в Новочеркасск, куда Каледина переводят в 1895 году на заурядную тыловую должность в Войсковой Штаб Донского Казачьего Войска.
Служба там продолжается пять лет, после чего произведенный в подполковники, а затем и в полковники – «за отличие» – Каледин состоит «при управлении 64[-й] пехотной резервной бригады», в 1903–1906 годах возглавляет Новочеркасское казачье юнкерское училище и вновь возвращается в Войсковой Штаб, теперь на должность помощника его начальника. Но о Каледине помнят не только как об администраторе или военном педагоге: в 1910 году он – к этому времени уже генерал-майор, и тоже «за отличие по службе», – ни дня не командовавший полком (одно из редких исключений!), принимает бригаду 11-й кавалерийской дивизии, а 12 декабря 1912 года (всюду дюжина – не счастливое ли это предзнаменование?) назначается начальником кавдивизии – и тоже 12-й. С ней он выйдет на Великую войну, за три месяца до начала грозных европейских событий будучи произведен в генерал-лейтенанты, и эти полки прославят его имя – или это он своим руководством даст дивизии немеркнущую славу одной из лучших в Императорской Армии?
Первые недели войны стали для русской конницы весьма ответственными: она должна была, выдвигаясь вперед, скрыть от противника мобилизационное разворачивание основных сил, – и с этой задачей справилась блестяще. Эмигрантский историк отмечал, что для австро-венгерского командования «прошло вообще необнаруженным» сосредоточение всей VIII-й армии, которой суждено будет стяжать едва ли не самую громкую известность на Юго-Западном фронте и во всех вооруженных силах Империи.
«12-й кавалерийской дивизии – умереть. Умирать не сразу, а до вечера!» – гласил, как рассказывали, приказ командующего VIII-й армией генерала А. А. Брусилова, отданный Каледину в августовский день 1914 года, когда дивизия своим самопожертвованием выручила остальные силы, и приказ этот многое говорит как о войсках, так и об их начальнике. За те бои Алексей Максимович был удостоен ордена Святого Георгия IV-й степени, а вскоре получил и Георгиевское Оружие – за участие в операции по взятию Львова, куда первыми вошли драгуны 12-й дивизии.
«Успех за успехом дал имя и дивизии, и ее начальнику, – писал впоследствии боевой товарищ Каледина генерал А. И. Деникин. – В победных реляциях Юго-западного фронта все чаще и чаще упоминались имена двух кавалерийских начальников, – только двух – конница в эту войну перестала быть “царицей поля сражения”, – графа Келлера и Каледина, одинаково храбрых, но совершенно противоположных по характеру: один пылкий, увлекающийся, иногда безрассудно, другой спокойный и упорный. Оба не посылали, а водили в бой свои войска. Но один делал это – вовсе не рисуясь, – это выходило само собой, – эффектно и красиво, как на батальных картинах старой школы, другой [ – ] просто, скромно и расчетливо. Войска обоим верили и за обоими шли».