Но одно дело, строить прожекты, а другое – предпринять практические шаги по интеграции Причерноморья. И «первую скрипку» в этом процессе играл даже не российский монарх, а крымские ханы.

Подписание Константинопольского мирного договора (того самого, который вырабатывала делегация Украинцева) между Османской империей и России положило начало тяжелейшему периоду в истории Крымского ханства.

Россия официально прекратила выплату ханам т.н. поминок (дани), а османы обязались удерживать крымцев от вторжений в пределы Российской империи. Вместе с тем Россия существенно снизила уровень своего дипломатического представительства в Бахчисарае, предпочитая решать вопросы по Крыму через голову ханов, напрямую с султанской администрацией.

Отсутствие военной добычи в первую очередь сказалось на причерноморских ногайцах, вассально зависимых от Крымского ханства. По словам известного российского историка Владимира Артамонова, в начале XVIII века ногайцы буквально метались в поисках нового протектора. Среди них периодически вспыхивали мятежи «против хана и турка».

В 1699 году взбунтовалась Буджакская орда, решившая получить «помочи и милости» от султана, московского царя или на худой конец от польского короля. Бунтовщиков возглавил бежавший из Крыма брат хана нурэддин Гази-Гирей.

Собрание важнейших мурз орды в декабре 1700 года просило султана отстранить от власти крымского хана Девлет-Гирея II. После того, как из Стамбула последовал отказ, Гази-Гирей обратился через гетмана Мазепу к «белому царю» принять его «з Белогородскою ордою в подданство». Однако, из-за нежелания обострять отношения с Османской империей в Москве Гази-Гирею также отказали. Начиналась Северная война со Швецией и на юге Петру нужен был мир.

В марте 1701 года крымское войско перешло через Днепр и стало громить ногайские улусы, истребив около 4 тыс. кочевников.

Аналогичный ответ Москвой был дан в 1702 году кубанским ногайцам, когда в Азов прибыл Кубек-мурза с просьбой о русском покровительстве.

В декабре 1702 года чрезмерно активно интриговавший против Москвы Девлет-Гирей II был низложен. В этих условиях вновь вспыхнул ногайский бунт в Бессарабии. Мурзы требовали военного похода на Россию и отстранённый от власти хан направился к ним за помощью. Османские гарнизоны в Очакове, Измаиле и Килие были осаждены сторонниками Гирея (около 60 тыс. человек).

Задумка мятежников состояла в том, чтобы в коалиции с османской «партией войны» восстановить хана у власти и идти войной на Азов и Киев. Однако этот план потерпел неудачу, поле мытарств на Северном Кавказе Девлет-Гирей II повинился перед новым ханом (своим отцом Хаджи-Селим-Гиреем) и был прощён.

В разгар последних событий (на рубеже 1702–1703 годов) на территорию гетманства прибыл носитель важной информации о внутренних процессах в Крымском ханстве.

Им был бывший валашский ротмистр, молдаванин Александр Давыденко. В 90-е годы он служил в Крыму и имел личное общение тогда ещё с калгой (вторая по значимости должность в иерархии ханства) Девлет-Гиреем. Давыденко поведал гетману Мазепе, как в одной из бесед Девлет-Гирей якобы сообщил ему, что готов вместе с беями «поклониться всемогущей царской державе и дале на турка воевати». Молдаванин предлагал свои услуги для налаживания прямого контакта царя и опального хана, а также в деле создания антитурецкой коалиции.

Мазепа счёл Давыденко авантюристом и уже собирался выслать его на родину, однако им заинтересовались в Москве. Более года он пробыл в российской столице, где им занимались Посольский и Малороссийский приказы. Давыденко удостоился приёма у канцлера Фёдора Головина, о нём осведомлялся сам царь, однако в условиях начавшейся Северной войны дальнейшего развития его предложения не получили. Валашский подданный получил сорок соболей ценой 50 рублей и был отправлен в Киев, где более года содержался Мазепой «под крепким караулом», а затем был выслан на Дунай.