18 мая основные силы благополучно достигли Петровского ретраншемента (фортификационное сооружение с внутренней оборонительной оградой). Туда для встречи с русским командующим и с просьбой о подданстве прибыли некоторые местные владельцы. Всем им был оказан теплый прием. Прошения о подданстве также были удовлетворены.

Продолжая поход в прежнем порядке, русские войска достигли Кубани и 25 мая начали переправу через реку на лодках и одновременное строительство моста. Переправившиеся части располагались на плацдарме в боевом порядке в готовности к отражению внезапного удара противника. Но горцы избегали открытого боя. Зато, воспользовавшись прибылью воды, они пустили по Кубани множество срубленных деревьев, которые разрушили мост и затруднили переправу. Тем не менее к исходу 29 мая весь Кавказский корпус переправился через реку, устроив инженерные укрепления и оставив для их охраны войсковые отряды с артиллерией по обе стороны переправы.

Дальнейший путь пролегал по местности, сильно пересеченной реками, ручьями и болотами. Приходилось ежедневно наводить по несколько мостов и гатей. 5 июня русские достигли Кубанского лимана, где их ждали трехдневный отдых и отряд войск, присланный туда из Таврического корпуса генерал-аншефа М.В. Каховского. Здесь был создан вагенбург (особый строй обозов в виде каре на случай нападения противника), после чего основные силы продолжили движение.

Первая стычка с неприятелем произошла 9 июня 1791 года на реке Нарпсухо, где черкесы и турки заблаговременно заняли позицию, рассчитывая задержать русских на подступах к крепости. Но после непродолжительного боя они отказались от своей затеи и отступили в Анапу. На следующий день к крепости подошли и войска Гудовича. Были заложены две батареи по 10 пушек каждая, которые с утра 14 июня открыли огонь по противнику. Причем одна батарея вела интенсивный обстрел крепости, а вторая — судов, находившихся на рейде. Батареи противника отвечали вяло, практически не чиня вред осаждавшим. В то же время под покровом ночи отряды черкесов то и дело совершали вылазки, которые сильно тревожили русских.

20 июня Гудович направил парламентера к анапскому коменданту Мустафе-паше с предложением сдаться, обещая за это свободно пропустить гарнизон и жителей со всем их имуществом. Но турки отвергли это предложение. Положение осадных войск было сложным. Им противостоял почти равный по силам гарнизон крепости, в тылу действовали отряды черкесов, постоянно нападавшие на фуражиров. В Черном море появилась неприятельская эскадра. В таких условиях время играло на пользу противника. Гудович решил не откладывать со штурмом, решив провести его в ночное время.

21 июня, собрав военный совет, командующий довел до подчиненных командиров план предстоящего штурма. Главный удар решено было нанести с фронта, где вал был ниже, а рвы не так глубоки, силами четырех колонн. Вспомогательный удар пятой колонны, составленной из частей Таврического корпуса, наносился со стороны моря. Зная, что во время штурма черкесские отряды непременно ударят в спину русским войскам, для охраны тыла также были выделены значительные силы. Всего в сражении принимало участие немногим более 12 тысяч человек, половина из которых предназначалась для действий на направлении главного удара, 1300 — на второстепенном направлении, 4144 человека для обороны тыла и 327 для защиты вагенбурга.

В тот же день, едва стемнело, штурмовые колонны выдвинулись на свои направления. В полночь загрохотали обе батареи. Неприятель, приняв передвижение и огонь русских за демарш, не предпринял ответных мер. Некоторые колонны смогли беспрепятственно приблизиться ко рву и начали его преодолевать. Лишь тогда осажденные разобрались в обстановке и бросились отражать штурм. Завязался жестокий бой, но русская пехота уже была на городских стенах и, истребив их защитников, спускалась в город. Подразделения подполковника Винова захватили средние ворота и опустили мост, по которому в город устремилась спешенная кавалерия. К утру гарнизон Анапы прекратил сопротивление. Более 8 тысяч защитников города были убиты, 13 500 человек «обоего пола» взяты в плен. Трофеями победителей стали 95 артиллерийских орудий, 3 булавы и 130 знамен, а также склады с военным имуществом и продовольствием. Потери русских составили 1238 убитыми и 2472 ранеными.

Награды для победителей были весьма щедры. Гудович получил орден Св. Георгия 2-й степени, а также шпагу, украшенную алмазами и изумрудами в виде лаврового венка. Четыре старших начальника удостоились ордена Св. Георгия 3-й степени, 6 человек — этого же ордена 4-й степени, еще 4 получили золотые шпаги, ряд офицеров стали кавалерами ордена Св. Владимира 3-й и 4-й степеней. «Остальные получили одобрительные листы, что не умаляет заслуг особенно отличившихся, так как одни из них уже были георгиевскими или владимирскими кавалерами, а другие, находясь в малых чинах, имели впереди много возможностей для дальнейших отличий и наград. Всем же вообще участникам знаменитого штурма было объявлено в высочайшем рескрипте на имя генерал-аншефа Гудовича монаршее благоволение».

В числе немногочисленных плененных защитников оказался и Шейх-Мансур. С четырьмя своими сподвижниками он был отправлен в Петербург, а затем сослан пожизненно в Соловецкий монастырь, где и умер в 1798 году. Последнее его письмо, обнаруженное в архивах профессором Оттино, было помечено «Соловец, 15 сентября 1798 года» и подписано «Джованни Батист Боэтти, проповедник».

Чеченские сподвижники Шейх-Мансура Хаджи-Гасан, Чагелезгин-Сулейман и едишкулец Пейдже-Али были сопровождены в Симферополь к генерал-аншефу М.В. Каховскому. Там было по их делу проведено следствие, «так как по сделанным допросам они не признались и не обличены ни в каком злом умысле, то Ее Императорское Величество, следуя всегдашнему ее в подобных случаях правилу — лучше даровать прощение преступнику, нежели наказать невинного, высочайше повелеть соизволила водворить их в Тавриде между людьми испытанной верности и, отыскав, доставить женатым их жен и детей».

После взятия Анапы русские войска некоторое время оставались в лагере, расположенном в окрестностях города. Вскоре Гудовичу стало известно, что противник без боя оставил крепость Суджук-кале. Направленные туда казаки подтвердили это. Они нашли крепость пустой и сожженной с 30 брошенными на валах орудиями. Заклепав пушки и сбросив их в море, русские оставили эту крепость и вернулись в главный лагерь.

4 июля 1791 года на рейде Анапы показался турецкий флот, состоявший из 52 судов. Но, убедившись, что крепость пала, флот ушел в открытое море. Но русское правительство и высшее командование видимо плохо знали обстановку. Из Петербурга поступило указание уничтожить Анапскую крепость. Следуя ему, Гудович приказал срыть укрепления до основания, а сам город предать огню. 11 июля русские войска начали обратное движение и спустя два месяца вернулись на свою территорию. После этого Кубанский корпус по приказу Г.А. Потемкина-Таврического был переведен в Екатеринославскую губернию и передан в состав армии генерал-аншефа Каховского.

После покорения Анапы Гудович занялся внутренними делами в подчиненном ему крае. 7 ноября он представил императрице всеподданнейший отчет, в котором достаточно четко оценил политическое состояние края и проживающих на его территории народов.