На исходе 1790 года ничем себя особо не проявившего генерала Булгакова сменил на посту командующего войсками 48-летний генерал-аншеф Иван Васильевич Гудович. Ему приказано было срочно выехать на Кавказскую линию и приложить особое усердие к «открытию самой ранней кампании на Анапу, дабы истребить сие гнездо турков, положить навсегда предел беспокойствам, которые Порта, подкупая и подущая закубанцев, в том крае производила».
Чрезвычайно важное значение, которое имела Анапа, объяснялось ее выгодным положением на северо-восточном берегу Черного моря. Кроме того, что в Анапе находился сильный турецкий гарнизон, из этой крепости постоянно велась религиозная и политическая пропаганда, побуждавшая номинально подвластные Турции закубанские народы к враждебным выступлениям против России. В конце января 1791 года генерал Гудович прибыл в Георгиевск и стал готовить войска к походу против Анапы. Генерал значительно усилил полевую артиллерию, пополнил транспортные средства для установки понтонных мостов, увеличил количество подвижных магазинов. Было исправлено снаряжение, обмундирование войск, приведены в порядок обозы, накоплены необходимые припасы.
Пока шли приготовления к походу, турки по-прежнему пытались всеми силами поднять против России мусульманское население края. В марте 1791 года султан вновь разослал фирман, в котором осуждал тех мусульман, кто окажется в бездействии в войне «правоверных» с «беззаконниками». Мустафа-паша из Анапы уверял горцев, что им собрано огромное войско. Он обещал в скором времени доставить деньги и требовал аманатов от кабардинцев. Шейх Мансур, который находился тогда в Анапе, рассылал собственные воззвания к горским народам, призывая к решительной борьбе с русскими. «Изъявляю вам искреннее почтение мое, — писал Мансур, — и советую очистить сердца ваши от пороков и ходить путем истины, по закону Божию. Ополчайтесь против беззаконных и мужественно наступайте на них. Я знаю достоверно, что война русских уже страшит; собираю теперь силы; и после прибытия сюда войск правоверных начну наступление на русских. Не бойтесь угроз их. Настало уже время ослабления беззаконных и торжества мусульман».
9 мая 1791 года генерал Гудович с 11 батальонами пехоты, двумя тысячами егерей, 24 эскадронами кавалерии и 20 орудиями двинулся к Анапе. На соединение с ним из Ейского укрепления вышел генерал-майор Загряжский с Кубанским корпусом. В его отряде насчитывалось четыре батальона пехоты, 20 эскадронов драгун, два донских казачьих полка и 16 орудий полевой артиллерии. 24 мая отряды соединились в восьми переходах от Анапы, у Талызинской переправы через Кубань, и приступили к наведению понтонного моста. Для установления постоянного сообщения с Кавказской линией и обеспечения войска фуражом Гудович устроил по правому берегу Кубани по всему пути следования войск ряд укрепленных постов и редутов с небольшими гарнизонами. Такие же укрепления устраивал и генерал Загряжский по пути своего следования из Ейской крепости. Главный опорный пункт и склад для войск Кавказского округа был сделан в укреплении Темижбек, а для войск Кубанского корпуса — в Ейском укреплении.
До 1787 года Анапа представляла собой большое поселение, окруженное всего лишь земляным валом. Перед самой войной по указанию султана Абдул-Хамида с помощью приглашенных французских инженеров тут была возведена настоящая крепость. Весной 1791 года она состояла из семи бастионов, соединенных куртинами. Перед стеной был вырыт глубокий и широкий ров, усиленный палисадом; этот ров обоими концами соединялся с морем. Со стороны моря Анапа была недоступна благодаря скалистым берегам и обширной морской отмели, которая не позволяла большим судам подходить к крепости. На стенах было установлено 83 орудия и 12 мортир крепостного калибра. Гарнизон Анапы насчитывал 10 тысяч турок и 15 тысяч вооруженных татар, ногайцев и закубанских черкесов. Командовал гарнизоном трехбунчужный Мустафа-паша. Военный флот с экипажем до трех тысяч человек прикрывал Анапу с моря.
В Анапе проживало до 20 тысяч мирных жителей. Это был многонациональный город. Кроме турок, здесь жили армяне, имевшие торговые лавки с большим количеством продуктов, так что крепость была полностью обеспечена провиантом, как и боеприпасами. Жили тут грузины, персы, греки, вокруг Анапы расположилось множество горских народов, а в окрестностях кочевали ногайцы. Подогреваемые воинственными призывами шейха Мансура, который имел сильное нравственное влияние на защитников крепости и окрестное население, закубанские народы, гарнизон Анапы и ее жители готовились к упорному сопротивлению.