Дальнейший путь пролегал по местности, сильно пересеченной реками, ручьями и болотами. Приходилось ежедневно наводить по несколько мостов и гатей. 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-й степеней. «Остальные получили одобрительные листы, что не умаляет заслуг особенно отличившихся, так как одни из них уже были георгиевскими или владимирскими кавалерами, а другие, находясь в малых чинах, имели впереди много возможностей для дальнейших отличий и наград. Всем же вообще участникам знаменитого штурма было объявлено в высочайшем рескрипте на имя генерал-аншефа Гудовича монаршее благоволение».