В конце мая 1789 года турки высадились на восточном берегу Черного моря и заняли пятитысячными отрядами крепости Анапу и Суджук. Опасаясь, чтобы турки не овладели Таманским полуостровом и не завязали отсюда связей с крымскими татарами, Потемкин-Таврический распорядился, чтобы Кубанский корпус был расположен на Таманском полуострове, а часть Кавказского корпуса была придвинута ближе к Кубани. Вследствие этого войска были распределены по Кубани следующим образом: в устье Лабы был поставлен отряд из 4-х батальонов, 8 эскадронов, 300 казаков при двух орудиях под командой генерал-майора Булгакова; при Темижбеке несколько меньшего состава отряд бригадира Депрерадовича; у Недреманного поста отряд генерал-майора Плагина; у Невинного мыса отряд бригадира Германа; наконец у Песчаного Брода расположился с 4 батальонами пехоты, 3 эскадронами кавалерии, 300 казаков и двумя орудиями сам Текеллий.
В июле на Кавказ прибыл новый главнокомандующий граф Салтыков, но он, не успевши ознакомиться с положением дел, был назначен командовать армией против шведов. Екатерина Вторая предоставила князю Потемкину назначить на Кавказ командующим войсками кого-либо из подчиненных ему генералов.
До назначения нового командующего старшим лицом в армии числился генерал-поручик Бибиков, заступивший таким образом фактически место командира в конце 1789 года. Узнавши, что турецкий султан Селим III отправил фирман лжепророку Мансуру о возбуждении горцев против России, Бибиков, под влиянием ложных сведений, сообщенных ему анапскими армянами, решил предпринять экспедицию в горы и с этой целью снарядил отряд в 7609 человек. В суровое зимнее время, 10 февраля 1790 года, он по льду перевел войска через Кубань и направил их во владения махошевцев. Горцы бросили свои жилища и скрылись в горы. Черкесы, жившие на Лабе, изъявили покорность. Отсюда отряд двинулся к темиргоевцам.
Но по мере того как войска углублялись в горы, горцы стали оказывать все большее и большее сопротивление. Под влиянием Мансура и турок они в свою очередь перешли в наступление, окружили отряд со всех сторон, появлялись с тыла, а впереди устраивали завалы и преграждения из срубленного леса. Отряд очутился в критическом положении. Сражаясь ежедневно с многочисленными партиями неприятелей, русские войска шли без дороги и проводников, по снегу и в стужу. Провиант и фураж были в недостатке; воду часто приходилось добывать нагреванием снега в солдатских котелках. Черкесы угоняли всюду скот и истребляли все, что могло служить продовольствием для людей и лошадей. Когда вышли сухари, пришлось резать обозных лошадей и довольствовать солдат одним лошадиным мясом. Только в некоторых аулах были найдены запасы проса, не истребленного черкесами. 15 марта отряд подошел к ущельям, которые выходили на равнину к Анапе, а 16 марта, вблизи р. Шебше турецкий двухбунчужный Мустафа-паша с 2000 человек преградил русскому отряду дорогу. После непродолжительного боя турки отступили, но затем четыре дня подряд войска выдерживали беспрерывные стычки с неприятелем, пока 21 марта отряд Бибикова не занял сел. Заны.
Здесь отряду был дан двухдневный отдых. 24 марта произведена была рекогносцировка Анапы, в которой считалось до 40 000 жителей и гарнизона. Русским удалось измерить глубину и ширину рва, окружавшего Анапу, но турки со своей стороны сделали вылазку из крепости. Завязался бой с гарнизоном, которым командовал Батал-паша. Турки не выдержали натиска русских, и одна часть их с Батал-пашой заперлась в Анапе, а другая, бывшая под командой Мустафы-паши, не успела попасть в крепость и отступила на Суджук-кале.
Под влиянием этой удачи Бибиков решил взять штурмом самую крепость, но приведению в исполнение плана помешала снежная буря. Она разразилась в ночь на 26 марта таким холодом, что в одну ночь пало 150 лошадей. Войска ослабели. «Все начальники, кроме меня, — рапортовал Бибиков, — такую получили простуду и ослабели, что ни к какому действию уже приступить не могли». 27 марта отряд генерала Бибикова оставил Анапу и отступил обратно. Начались новые бедствия: разливы горных речек мешали движению войска. Целых 15 дней, с 27 марта по 11 апреля, войска прошли всего 120 верст, т. е. по 8 верст в сутки. Провианта не было. Войска питались кониной, кореньями и травой.
По распоряжению князя Потемкина, до которого дошли слухи о бедствиях экспедиции Бибикова, командир Кубанского корпуса барон Розен послал отряд из 600 драгун для розыскания экспедиции. Наконец, 4 мая войска ее в ужасном состоянии появились у Григориополиса. Офицеры и солдаты, по словам генерала Розена, «были изнурены сверх человеческого терпения стужей и ненастьем, от которых ничего для укрепления себя не имели; босы, в рубах и без всякой нижней, а в беднейшей верхней одежде, которая вся сгнила и изодрана. Больные, едва имея дыхание, опухли, да и те, кои считаются здоровыми, немного от них рознятся и в самых слабейших силах; полки и артиллерия потеряли лошадей, а вообще весь корпус крайне расстроен».