Сосредоточив 4 мая 1791 г. у Темишбека 11 батальонов пехоты, 1900 егерей, 24 эскадрона и 20 орудий, всего около 10 тысяч человек, Гудович 9 мая двинулся к Талызинской переправе через Кубань, где к нему 24 мая присоединился генерал-майор Загряжский с отрядом из 4 батальонов, 20 эскадронов драгун, двух донских казачьих полков и 16 орудий.
Снабдив войска 40-дневным продовольствием, Гудович перешел Кубань и двинулся к Анапе. В одном переходе от нее у д. Адалы 8 июня к нему присоединился высланный из Крыма через Тамань отряд генерал-майора Шица, состоявший из 800 егерей, 10 эскадронов, 300 донских казаков и 14 орудий При отряде было 90 штурмовых лестниц. На следующий день, продолжая движение, наши войска наткнулись в 4 верстах от Анапы на несколько тысяч человек, пытавшихся воспрепятствовать переправе наших войск через горную речку. Авангардом бригадира Поликарпова черкесы были рассеяны, и главные силы беспрепятственно остановились в виду Анапы.
Анапа издавна была центром, из которого распространялась среди горцев религиозная пропаганда турок. В 1784 г. она была обращена в крепость, состоявшую из 7 бастионов, соединенных куртинами; ров, упиравшийся своими концами в море, имел каменные одежды. Протяжение рва было около 700 сажен, за крепостным валом был устроен палисад. Гарнизон крепости состоял из 10 тысяч турок и 15 тысяч разных горских народов. В крепости было 83 пушки и 19 мортир. Со стороны моря кроме скалистых берегов крепость обеспечивалась еще большим числом мелких вооруженных судов. Начальником гарнизона был трехбунчужный Мустафа-паша. В Анапе же находился и шейх Мансур, который своими пророчествами возбуждал население к упорному сопротивлению.
12 июня Гудович приказал заложить три батареи на 32 орудия, причем одна из них находилась всего в 250 сажен от крепостного вала. Несмотря на частые вылазки неприятеля и огонь из крепостных орудий, затруднявшие работы, к 10 июня батареи были окончены и по крепости открыт огонь, который вызвал пожар в разных частях города, продолжавшийся до рассвета 20 июня. Утром 20 июня Гудович отправил Мустафе-паше письмо, в котором предлагал ему сдать крепость, обещая свободный выход гарнизону и жителям. Подстрекаемые Мансуром турки в ответ на это письмо открыли огонь по нашим войскам.
Не имея осадной артиллерии, Гудович решил овладеть Анапой штурмом. Произведя рекогносцировку, он обнаружил, что правая половина крепостного вала и рва имела меньший профиль, вследствие чего и было решено вести главную атаку на эту часть крепости.
С наступлением ночи 21 июня лагерь был снят и войска разведены по местам, с которых должны были начать атаку. Войска были разделены на пять колонн, начиная с левого фланга: 1-я и 2-я под начальством генерала Булгакова, 3-я и 4-я под начальством генерала Депрерадовича и 5-я генерала Шица. Общий резерв был под начальством бригадира Поликарпова.
В полночь Гудович приказал открыть огонь со всех батарей, и под его прикрытием атакующие колонны стали приближаться к крепости. В час ночи стрельба батарей была прекращена. За полчаса до рассвета снова был открыт обстрел города и войска двинулись на штурм. Неприятель заметил их только тогда, когда первые две колонны наткнулись у крепостного рва на один из пикетов. Турки бросили в ров несколько светящихся ядер и открыли почти в упор картечный огонь. Несмотря на это, наши войска спустились в ров и стали приставлять лестницы.
Четвертая колонна, предводительствуемая полковником Самариным, первой взошла на неприятельский вал и, невзирая на отчаянное сопротивление, утвердилась на нем.
Вторая колонна полковника Муханова овладела бастионом, но первая колонна полковника Чемоданова встретила большие препятствия и была выведена из затруднительного положения только подоспевшим резервом. Турки были вытеснены из кавальера, и русские открыли огонь по городу.
Еще большие затруднения встретила пятая колонна. Ей предстояло спуститься вниз по берегу и, водою обогнув оконечность вала, атаковать крепость со стороны моря. Вместо того чтобы подойти скрытым, генерал Шиц отправил на лодках 50 егерей, с тем чтобы отвлечь внимание неприятеля с морской стороны. Егеря слишком рано открыли огонь и тем привлекли внимание турок. Колонна Шица была встречена столь сильным огнем, что не смогла дойти до контр-эскарпа и стала отступать. Вызвав резерв, Шиц сам стал во главе колонны и повел ее вперед. Поддержанный из резерва Гудовичем, выславшим на помощь всю кавалерию под командою бригадира Поликарпова, Шиц овладел крепостным валом.
Турки в течение 5 часов защищались отчаянно, и успех штурма был сомнителен, пока Гудович не ввел в дело остатки резерва, которые склонили победу на нашу сторону, и в 8 часов утра 22 июня Анапа сдалась. Трофеями были 96 орудий, 130 знамен, значительные боевые и продовольственные припасы. Неприятель потерял убитыми и ранеными до 8 тысяч человек, до 14 тысяч жителей сдались пленными и в их числе Мустафа-паша и шейх Мансур. Наши потери были 930 убитыми и 1995 ранеными.