Произведенный Деникиным в генералы, Кутепов со своей дивизией взял Новороссийск и на некоторое время остался в городе генерал-губернатором. В Советском Союзе было принято обвинять Александра Павловича в жесточайших репрессиях против пролетариата, его даже называли «березовым» генералом. Молва приписывала ему такое высказывание. Когда привели пойманного большевистского агитатора, Кутепов сказал своим офицерам: «Если бы здесь росла береза, я бы приказал его повесить. А так — придется расстреливать, можно прямо здесь». Но жестокость Кутепова сильно преувеличена. К примеру, в эмиграции считали, что зачастую генерал, наоборот, был мягок. Поводом для этих разговоров послужил такой случай. Начальник штаба новороссийского гарнизона полковник де Роберти был осужден за взятку. И хотя Кутепов за такие преступления расстреливал (с бюрократами по-другому не справиться, говорил генерал), в тот раз он ограничился лишь заключением чиновника в тюрьму. Когда же в Новороссийск вошли части Красной армии, де Роберти был немедленно освобожден, а потом долгие годы служил в иностранном отделе ОГПУ.
В конце января 1919 года Александр Павлович снова был вызван на фронт, где принял командование 1-м армейским корпусом. Именно под его руководством Добровольческая армия, не обладая численным превосходством, взяла Харьков, Курск и
Орел. Уже в эмиграции бывшие белые офицеры считали, что это стало возможным только благодаря действиям Кутепова. Его спокойствие и выдержка даже в самые тяжелые минуты были хорошо известны всем добровольцам. Но особенно отчетливо эти качества Александра Павловича проявились уже в Галлиполи, куда русская армия эвакуировалась из Крыма. Барон Врангель был изолирован французами. Поддержанием духа офицеров занимался генерал Кутепов. Было сделано главное — потерпевшая поражение армия продолжала верить в свою правду. Были сохранены дух и воля к дальнейшему сопротивлению. Кто-то из бывших офицеров вспоминал уже в эмиграции: «В один из самых страшных моментов нашей белой жизни, в момент, казалось бы, предельного провала, на пустынной и суровой земле, в далекой чужбине вновь завеяли наши старые военные знамена. В «голом поле» день и ночь, беспрерывной сменой молчаливых русских часовых совершалась литургия Великой России!»
С самого утра, как рачительный хозяин, генерал Кутепов обходил своим неутомимым шагом весь городок и лагерь. Он всегда был тщательно одет, бодр и весел духом, словно окружающая обстановка самая обычная. Задерживался около тех, кто выполнял наиболее трудную и грязную работу. Со всеми здоровался. «У меня руки грязные, Ваше Высокопревосходительство», — говорил кто-нибудь из офицеров. «Руки грязнятся не от работы, — отвечал Александр Павлович и крепко пожимал руку.