Для Алексеева очень тягостными оказались непредвиденные известия о занятии Екатеринодара красными и об отступлении из города кубанского атамана с Войсковым правительством, Радой и Кубанским правительственным отрядом. Теперь все его доводы, убеждения в важности похода на Кубань, казалось бы, теряли смысл. Теперь сторонники отхода «на зимовники» могли упрекнуть генерала не только в порочности его военно-политических расчетов, но и в настоящем авантюризме. Но этого не произошло. Авторитет Алексеева оставался прежним. Части Добровольческой армии, соединившись с отрядами кубанских казаков и горцев 14 марта в ауле Шенджи, стали готовиться к штурму столицы Кубани. От кубанского правительства казна армии пополнилась миллионом рублей.
Во время переговоров о присоединении Кубанского правительственного отряда к Добровольческой армии произошел характерный эпизод, описанный А. Сувориным. Алексеев, как и Корнилов, настаивал на обязательном подчинении кубанских частей единому командованию (хотя в будущем не исключалось выделение Кубанской армии). Согласовывая порядок вхождения кубанцев в состав Добрармии, начальник отряда, недавно произведенный в генералы полковник В.Л. Покровский отметил, «что кубанское правительство много поработало над созданием своей армии и на нее произвело бы дурное впечатление, если бы она увидела, что ее передали “пришельцам”. Он выразился, — отмечал Суворин, — именно так, вообще очень неудачно по форме; оратор он плохой.
Алексеев вспылил, хлопнул по столу своей фуражкой и сказал:
— Вы… не знаю как Вас величать: полковник или генерал (Покровский был без погон), говорите от лица своего самолюбия и только! И мы могли бы сказать кое что о трудах, положенных нами на создание Добровольческой армии, но теперь не время считаться личными претензиями. Надо говорить об общих интересах общего дела! А что до недовольства будто бы Кубанской армии с переводом ее в состав армии Добрвольческой, то я должен сказать, что она почти вся уже сама перешла!»
После выхода добровольцев из аула в направлении на станицу Ново-Дмитровскую наступил самый тяжелый период похода, заслуженно названного позднее «Ледяным». Атака на станицу началась при обильном снегопаде, под порывистым, промозглым ветром. Как отмечал Суворин, «Алексеев, несмотря на свою болезнь, так же как и все другие, перенес это испытание и каким-то чудом не заболел». Сохранились не менее колоритные воспоминания участника похода И. Патронова, отмечавшего, что 15 марта наступил один из особенно «трагических моментов Кубанского похода», когда «перед разлившимся ручьем, под артиллерийским огнем из станицы Ново-Дмитриевской, скопились пехота, артиллерия, конница, обоз. Пехота переправлялась на крупах лошадей и частью вброд, конница — по покрытому разливом мосту и вброд, а обозы и артиллерия совершенно застряли, ибо разлив усилился и переправа стала невозможной. В 2-х верстах — Станица, где шел бой. Среди повозок, орудий, лошадей стояла одинокая фигура генерала Алексеева, по случайному совпадению в этот момент оставленному своими приближенными. Старик дрожал от холода, изыскивая способы для переправы оставшихся людей и лошадей. А метель все усиливалась, ослепляя и занося группу отставших, плохо одетых и замерзающих людей. Шекспировский король Лир, изгнанный дочерьми и скитающийся в лесу во время бури, представляет трагическую фигуру… Но… в описываемый момент не менее трагична была фигура первого русского генерала, хлопочущего над разрешением задачи невозможной переправы».
26 марта армия переправилась через Кубань и на следующий день начала атаки предместий Екатеринодара. Алексеев со своими помощниками и большей частью обоза сначала остановился в станице Елизаветинской. Затем генерал с несколькими адъютантами переехал в колонию Гначбау и остановился в доме близ пивоваренного завода. Труба завода, однако, оказалась хорошим ориентиром для красной артиллерии, и однажды снаряд полностью разнес дом штаба. Погибли трое офицеров. Алексеева спасло лишь то, что в этот момент он находился во дворе.
Каждый день он выезжал на позиции и останавливался в роще, недалеко от «корниловской» фермы. Интересные воспоминания сохранил по этому поводу Богданов. Он писал: «Мне кажется, что генерал Алексеев немного завидовал Корнилову в его боевой деятельности. Он приезжал каждый день на ферму (где располагался штаб Корнилова. —