Наряду с небывалой жертвенностью и бескорыстием в ряды Добровольцев, по их собственным признаниям, уже в первый период борьбы стали проникать семена жестокости и кровожадности. Многие офицеры, испытав унижения и преследования, потеряв в огне революции родных и близких и с трудом прорвавшись в Добровольческую Армию, горели желанием «отвести душу». Кутепов не поощрял – и не удерживал. Но когда в Армию хотел поступить прапорщик Т. Кирпичников – бывший унтер-офицер, считавшийся (быть может, неоправданно) зачинщиком бунта запасного батальона Лейб-Гвардии Волынского полка в феврале 1917 года, – Кутепов сказал лишь: «А, вы тот унтер-офицер, который убил своего начальника…» – и приказал его расстрелять. Некоторые армейские офицеры, особенно из интеллигенции, приписывали особую жестокость именно Гвардейцам: «…Крестьянские трупы загородят нам все дороги, и с гвардии полковником Кутеповым мы именно поэтому не дойдем не только уж до Московского Кремля, а, может быть, и до ближайшей деревни». Но справедливость этой оценки сама по себе спорна, да и в условиях борьбы на истребление противника кутеповская позиция была едва ли не самой эффективной…
После соединения с Кубанским отрядом генерала В. Л. Покровского 17 марта Добровольческая Армия была переформирована. Командовавший Офицерским полком генерал С. Л. Марков принял 1-ю бригаду, его помощник полковник Н. С. Тимановский вступил в командование полком, а помощником командира полка стал Кутепов. Когда же при штурме Екатеринодара погиб командир Корниловского ударного полка полковник М. О. Неженцов, Александр Павлович был назначен его преемником, вероятно, по инициативе А. И. Деникина. С Ледяного похода началось сближение Кутепова и Деникина, основанное на определенном сходстве характеров и взаимной симпатии, «чтобы в горниле Гражданской войны перерасти в большую приязнь, а в эмиграции – в исключительно доверительные отношения». На момент вступления Кутепова в должность Корниловский полк насчитывал менее 300 штыков, а к концу боев под Екатеринодаром сократился до 67 невредимых бойцов; в 1-й роте осталось всего четыре человека.
Почти сразу после прорыва Добровольческой Армии из почти безнадежного окружения очевидной стала отчужденность Корниловцев по отношению к их новому командиру. Неприязнь ударников, многие из которых были настроены республикански, а иные даже симпатизировали эсерам, явно выплескивалась на Гвардейцев-монархистов. Кутепов остро почувствовал себя чужаком (хотя в свое время и у Преображенцев считался «пришлым») и собирался уйти из Корниловского полка. Однако его помощник, недавний командир 2-го батальона капитан Н. В. Скоблин, сумел не только уговорить Александра Павловича остаться, но и помог ему получить искреннее признание подчиненных. С тех дней Кутепов стал «кровно связан» с Корниловцами, а со Скоблиным, который был моложе его на десять лет, постепенно крепко сдружился.
Тем не менее во Второй Кубанский поход Александр Павлович выступил уже командиром бригады во 2-й дивизии генерала А. П. Богаевского. Постоянно находясь во время боев в цепях Корниловского полка, он еще более укрепил свой авторитет среди «несгибаемых» и был признан ими окончательно. После гибели 12 июня под станцией Шаблиевской генерала Маркова Кутепов временно исполнял должность начальника 1-й дивизии, но 15 июля дивизию принял генерал Б. И. Казанович – этот, как характеризовал его Деникин, «отличный таран для лобовых ударов», чья тактика фронтальных боев станет вскоре одной из причин больших потерь, понесенных дивизией под Екатеринодаром, Армавиром и Ставрополем.
В конце тяжелого боя под Тихорецкой Кутепов едва не пал жертвой провокации: красные выбросили белый флаг, а когда полковник с несколькими сопровождавшими подскакал к их окопам, открыли огонь и перебили часть офицеров. Неудивительно ожесточение Кутепова, который впоследствии, по ряду сообщений, не раз обходил шеренги пленных и лично выбирал, кого следует расстрелять (отбор жертв по принципу «а морда самая комиссарская» был достаточно типичен для начального периода борьбы…).
16 июля авангард 1-й дивизии во главе с Кутеповым разбил передовые красные части И. Л. Сорокина у станицы Тимашевской. Через день полковник с Кубанским стрелковым и частью Марковского полка выступил к станции Сосыка, чтобы перехватить тридцатитысячную группу противника и не позволить ей прорваться на защиту Екатеринодара. Однако Сорокину удался скрытный маневр, благодаря которому он вышел в тыл наступающим на Кубанскую столицу Добровольцам. Для спасения положения в район Выселки – Кореневская командование бросило все наличные силы, в том числе и группу Кутепова от Кущевки и Сосыки. В тяжелых боях 28 июля – 2 августа потери были велики, в частности, по оценке современника, «лег весь цвет Марковского офицерского полка». Но 3 августа 1918 года Екатеринодар был взят.
Буквально через несколько дней, как только Добровольцы заняли Новороссийск, Кутепов получил назначение Черноморским генерал-губернатором и 13 августа приступил к исполнению обязанностей. Оно может быть воспринято как свидетельство сложности политической ситуации в Добровольческих кругах: именно в августе группа Гвардейцев во главе с Кутеповым, по свидетельству В. В. Шульгина, открыто поддержала монархические выступления последнего, заявив: «Теперь мы знаем, за что мы боремся!» – и вызвав неудовольствие Деникина. Впоследствии Главнокомандующий, не указывая даты, но явно имея в виду этот случай, вспоминал, как «Кутепов на почве брожения среди гвардейских офицеров, недовольных “лозунгами” армии, завел речь о своем уходе», но после уговоров остался. Напрашивается предположение о каком-то конфликте, возможно, не без участия либерально настроенного начальника Штаба Армии, генерала И. П. Романовского, враждовавшего с ярым монархистом полковником М. Г. Дроздовским. В свете этого отправка Кутепова на тыловую должность могла означать не желание А. И. Деникина и М. В. Алексеева вручить власть твердому прагматику или поберечь верного сторонника в условиях нарастающей ожесточенности боев, а стремление притушить противостояние или даже «почетную ссылку»…
Административно-хозяйственный опыт Кутепова прежде ограничивался уровнем командира полка, но на его стороне были трезвый житейский расчет, решительность и кристальная честность. Почти не взаимодействуя вначале с деморализованными местными чиновниками, губернатор всеми силами старался избежать пороков традиционной бюрократии. Смело ломая обычаи, своим приказом он образовал первое в России подлинно бессословное земство; это стало признанием реальности и необратимости послефевральских перемен в стране. Твердой рукой Кутепов подавлял враждебные режиму движения, прежде всего, разумеется, большевицкие. Говорили, что в Новороссийске виселице пустовать не доводилось; но на нее чаще попадали дезертиры, бандиты и мародеры, и потому большинство горожан, побаиваясь грозного полковника, все же жило спокойно. Жители проникались даже благодарностью за постоянные отмены Кутеповым денежных взысканий, которые пытались накладывать на население наиболее ретивые чинуши. В довершение всего Губернатор пресек попытки вывоза немцами из города закупленного сырья и не пропускал их в Штаб Добровольческой Армии, выполняя распоряжение командования – «Никакого сотрудничества с немцами».
Осуществляя в своей «Кутепии», как стали называть Черноморское генерал-губернаторство, типичную военную диктатуру – единственно возможную линию в тех условиях, – Александр Павлович не обращал никакого внимания на резкую критику либеральной интеллигенции. Скрытую антипатию проявляли и торгово-финансовые круги, лишенные возможности обогащаться путем хищений и спекуляций, столкнувшись с аскетизмом и неподкупностью Кутепова, который за предложение взятки повесил бы любого. Доказательством щепетильной порядочности генерал-губернатора служит отсутствие порочащих его слухов – в отличие от появлявшихся впоследствии многочисленных красочных описаний, достоверных или выдуманных, шумных кутежей генералов В. З. Май-Маевского или А. Г. Шкуро.
В Новороссийске же Кутепов неожиданно для самого себя был очарован молоденькой дочерью коллежского советника Лидией Давыдовной Кют (несмотря на немецкую фамилию, Православного вероисповедания) и женился на ней. А 12 ноября 1918 года он получил приказ о производстве в генерал-майоры – за боевые отличия.
Между тем Добровольческая Армия, после объединения с Донской под общим командованием генерала Деникина и наименованием Вооруженных Сил Юга России, в результате этого объединения была втянута в изнурительные кровопролитные бои в Донецком бассейне. Красная Армия становилась организованной силой, Добровольцы же не имели резервов и были весьма скудно снабжены и обмундированы, что особенно сказывалось в условиях сильных морозов. 13 января 1919 года состоялось назначение А. П. Кутепова командующим 1-м армейским корпусом вместо генерала Б. И. Казановича. В январе – марте отряды Добровольческой Армии сдерживали натиск противника в районе Дебальцево – Таганрог; с 15 апреля Кутепов воевал на Царицынском направлении, а 6 мая прибыл под Ростов.
Он не скрывал радости от назначения (ибо генерал-губернаторская деятельность была для него все-таки чуждой), хотя фронт ему достался почти безнадежный. В те дни на всех, с кем он встречался, «небольшого роста, коренастый, с черной густой бородкой и узкими, несколько монгольского типа глазами, генерал Кутепов производил впечатление крепкого и дельного человека». Он сразу же взял корпус в свои железные руки и смог воодушевить потрепанные полки категорической требовательностью и деловитым спокойствием. Враг понял опасную силу личности Кутепова, и следствием стала «адская машинка», подброшенная в генеральский вагон. А в умах и сердцах Добровольцев весенние успехи (напор красных ослабел, и они были отброшены от Ростова) связывались исключительно с новым командиром: «Кутепов объезжал части и говорил о предстоящем походе. От него веяло уверенностью в победе. “Не надейтесь на танки, – говорил он, – дело не в технике, а в силе духа”».