В конце мая 1789 года турки высадились на восточном берегу Черного моря и заняли пятитысячными отрядами крепости Анапу и Суджук. Опасаясь, чтобы турки не овладели Таманским полуостровом и не завязали отсюда связей с крымскими татарами, Потемкин-Таврический распорядился, чтобы Кубанский корпус был расположен на Таманском полуострове, а часть Кавказского корпуса была придвинута ближе к Кубани. Вследствие этого войска были распределены по Кубани следующим образом: в устье Лабы был поставлен отряд из 4‑х батальонов, 8 эскадронов, 300 казаков при двух орудиях под командой генерал-майора Булгакова; при Темижбеке несколько меньшего состава отряд бригадира Депрерадовича; у Недреманного поста отряд генерал-майора Плагина; у Невинного мыса отряд бригадира Германа; наконец у Песчаного Брода расположился с 4 батальонами пехоты, 3 эскадронами кавалерии, 300 казаков и двумя орудиями сам Текеллий.

В июле на Кавказ прибыл новый главнокомандующий граф Салтыков, но он, не успевши ознакомиться с положением дел, был назначен командовать армией против шведов. Екатерина Вторая предоставила князю Потемкину назначить на Кавказ командующим войсками кого-либо из подчиненных ему генералов.

До назначения нового командующего старшим лицом в армии числился генерал-поручик Бибиков, заступивший таким образом фактически место командира в конце 1789 года. Узнавши, что турецкий султан Селим III отправил фирман лжепророку Мансуру о возбуждении горцев против России, Бибиков, под влиянием ложных сведений, сообщенных ему анапскими армянами, решил предпринять экспедицию в горы и с этой целью снарядил отряд в 7609 человек. В суровое зимнее время, 10 февраля 1790 года, он по льду перевел войска через Кубань и направил их во владения махошевцев. Горцы бросили свои жилища и скрылись в горы. Черкесы, жившие на Лабе, изъявили покорность. Отсюда отряд двинулся к темиргоевцам.

Но по мере того как войска углублялись в горы, горцы стали оказывать все большее и большее сопротивление. Под влиянием Мансура и турок они в свою очередь перешли в наступление, окружили отряд со всех сторон, появлялись с тыла, а впереди устраивали завалы и преграждения из срубленного леса. Отряд очутился в критическом положении. Сражаясь ежедневно с многочисленными партиями неприятелей, русские войска шли без дороги и проводников, по снегу и в стужу. Провиант и фураж были в недостатке; воду часто приходилось добывать нагреванием снега в солдатских котелках. Черкесы угоняли всюду скот и истребляли все, что могло служить продовольствием для людей и лошадей. Когда вышли сухари, пришлось резать обозных лошадей и довольствовать солдат одним лошадиным мясом. Только в некоторых аулах были найдены запасы проса, не истребленного черкесами. 15 марта отряд подошел к ущельям, которые выходили на равнину к Анапе, а 16 марта, вблизи р. Шебше турецкий двухбунчужный Мустафа-паша с 2000 человек преградил русскому отряду дорогу. После непродолжительного боя турки отступили, но затем четыре дня подряд войска выдерживали беспрерывные стычки с неприятелем, пока 21 марта отряд Бибикова не занял сел. Заны.

Здесь отряду был дан двухдневный отдых. 24 марта произведена была рекогносцировка Анапы, в которой считалось до 40 000 жителей и гарнизона. Русским удалось измерить глубину и ширину рва, окружавшего Анапу, но турки со своей стороны сделали вылазку из крепости. Завязался бой с гарнизоном, которым командовал Батал-паша. Турки не выдержали натиска русских, и одна часть их с Батал-пашой заперлась в Анапе, а другая, бывшая под командой Мустафы-паши, не успела попасть в крепость и отступила на Суджук-кале.