Вторая турецкая война снова вызвала Гудовича на ратное поле. Командуя отдельным отрядом, он взял укрепленное место Гаджибей (нынешняя Одесса), затем принудил к сдаче крепость Килию и подступил к Измаилу. Но Измаил был не Килия и не Гаджибей. Грозные стены его защищались сорокатысячным гарнизоном под начальством мужественного сераскира, решившегося умереть, а не сдаться. 20 ноября Гудович донес Потемкину, что овладеть Измаилом в настоящем году невозможно. Потемкин ответил присылкой Суворова – и неприступная крепость была взята штурмом. Гудович уже не участвовал в этом приступе: он был отозван в главную квартиру, где некоторое время состоял без должности. Между тем императрица пожаловала ему за взятие Килии чин генерал-аншефа, а вслед за сим, 12 ноября 1790 года, назначила его кавказским наместником.
Гудович прибыл в резиденцию наместничества, в город Георгиевск, 26 января 1791 года, а спустя несколько месяцев он уже блестяще вписал свое имя в летописи Кавказских войн покорением Анапы – этого крепкого разбойничьего гнезда, высылавшего на русские пределы целые орды хищных горцев и уже два раза заставившего русские войска испытать неудачу.
Нашествие Батал-паши было свежо в памяти Кавказских войск и убеждало Гудовича в необходимости скорейшего разрушения этого разбойничьего притона. И скоро он, во главе пятнадцати батальонов и двух казачьих полков с пятьюдесятью орудиями, был под стенами Анапы.
Участь крепости была решена 22 июня 1791 года. Рекогносцировки убедили наместника, что крепость с суши превосходно защищена семью бастионными фронтами, соединенными между собой куртинами; что широкий ров, опоясывая ее полукругом и упираясь своими концами в обрывистый берег Черного моря, достигает нескольких саженей глубины, выложен камнем, а в некоторых местах даже просто высечен в каменистом грунте. Гудовичу известно также, что Анапу защищает пятнадцатитысячный отборный турецкий корпус и что в городе находится известный агитатор Шейх-Мансур, присутствие которого, по его влиянию на умы мусульман, могло заменить собой не одну тысячу войска.
Ночью 16 июня Гудович обложил Анапу, а на следующий день с утра батареи открыли по ней огонь. Гудович торопился с приступом, сознавая, что положение его корпуса может сделаться отчаянным. Перед ним были грозные твердыни, уже видавшие перед собой русские силы. За ним собирались отчаянные полчища горцев, готовые отрезать отступление или броситься в тыл русским, чтобы поставить их между двумя огнями. К тому же имелись сведения, что турецкий флот спешит на помощь Анапе и что он уже только в двух или трех переходах от нее.
День 21 июня прошел в приготовлениях к штурму. Войска разделились на четыре колонны, из которых одна, под командой генерала Загряжского, расположившись тылом к Анапе, приготовилась отражать нападение горцев, а остальные, под начальством генералов Булгакова, Депрерадовича и барона фон Шица, назначались на приступ. Гудович ездил по войскам и воодушевлял солдат рассказами о грозном измаильском штурме; и солдаты, вдохновляясь на этой глухой окраине отечества славой своих далеких сослуживцев, кипели желанием боя и обещали друг другу или взять Анапу, или умереть под ее стенами. В их положении, впрочем, другого выхода и не было.
В глухую полночь с 21 на 22 июня со всех русских батарей началась жестокая канонада. Турки отвечали не менее сильным огнем. И русские колонны при громе пушек и шуме морского прибоя двинулись к Анапе.
Первые две колонны, спустившись в ров и приставив лестницы, быстро, «по-измаильски», взобрались на стены и, несмотря на стойкое сопротивление турок, проникли в крепость. Третья колонна, генерала Шица, попала под сильный перекрестный огонь и была отброшена назад с огромным уроном. Но, устроившись, она повторила атаку и после жестокого боя утвердилась на правом бастионе. Воодушевление русских войск было так велико, что многие начальники, например полковники Чемоданов, Муханов, Келлер, Веревкин, Самарин, граф Апраксин и подполковник Нелидов, будучи ранены, и иные по несколько раз, не оставили строя. Гудович обратил особенное внимание на артиллерийского майора Меркеля, старого георгиевского кавалера, которому ядро раздробило руку и который, несмотря на это, до конца распоряжался действиями своих батарей.
