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