Но посольству, всё же удалось отбиться от нападавших, и добраться до владений крымского хана. Другому послу, князю Фёдору Ромодановскому повезло меньше. Его не только ограбили, но и взяли в плен, продав в Кафу, откуда он был выкуплен великим князем. Прибывший в Крым князь Кубенский жаловался хану Менгли Гирею на разбои азовских казаков. Хан в свою очередь писал о том турецкому султану и кафинскому паше, прося удовлетворить обиды русского посла и его свиты.
В этом же 1500 г., согласно работе украинского историка Ивана Кипрякевича «Взгляд на историю Украины», появляется первое упоминание о запорожских казаках, чьи зимовники располагались за днепровскими порогами. Это замечание весьма важно для изучения донского казачества, ибо оно, на протяжении столетий, не раз пополнялось низовыми запорожскими черкасами, и к этому времени могли иметь зимовники на Дону. Но первый, исторически зафиксированный факт пребывания запорожцев на Дону, мы находим в грамоте польского короля Стефана Батория от 20 августа 1576 г. В ней подтверждались права и вольности «низового запорожского казачества», расширенные в 1516 г.. За низовыми казаками вновь были закреплены земли, лежащие вниз по Днепру и Бугу вплоть до лиманов: «як из виков бувало по Очаковские улуси, и в гору реки Богу (Буга) по речку Синюху. От самарских же земель, через степь, до самой реки Дону, где ещё за гетмана казацкого Предслава Лацкорунского казаки запорожские свои зимовники мевали (имели)». Следовательно, уже при втором казачьем гетмане, запорожские черкасы, если и не полностью владели низовьями Дона, то контролировали их.
Здесь следует отметить одну особенность формирования запорожского казачества. Польско-литовские короли жаловали пустующие запольные земли вольным людям, для их последующего заселения и переводили их в казачье сословие. В качестве примера можно привести королевскую грамоту выданную Науму Кобелю: «Имеет Наум право людей к себе звать на те места, не тяглых и не письменных, добрых и не ябедников, не воров и не разбойников, которые из городов и волостей выбиты».
1501 г. Посол великого князя, бывший в этом году в Крыму, доносил в Москву отпиской, что «сын турского (султана) магметсалтан кафинской сее весны посылал ратью людей своих на чекасы триста человек, да двести человек черкас (здесь скорее всего речь идёт о черкесах) с ними же ходили, которые у кафинского служат».
1503 г. Азовские турки, соединившись с азовскими казаками, подстерегли в степи и ограбили русское посольство великого князя Ивана 3. Тот, узнав об этом, отправил хану Менгли Гирею грамоту с жалобой на бесчинства казаков: «от казаков на поле страх», и потребовал покарать их. Хан в свою очередь уведомил об этом турецкого султана: «ныне гораздо отведал есьми в князя Ивановых послов и гостей, и водою и полем дорог стерегли и грабили наши азовские люди с казаками одиначившись». Узнав об этом, султан велел крымскому хану и своему сыну – кафинскому султану Магмету навести в Азове порядок: «чтобы они всех неблагонамеренных в Азове пашей, турок и казаков переловили и главнейших казнили бы».
Из донесения посла Заболоцкого становиться известно, что во исполнение воли султана «Менгли Гирей отпускает в Азов своего сына, Бурнаша и с ним 1000 человек, чтобы переловить всех казаков, какие бы в Азове не были». Прибыв в Азов Бурнаш, выбил из города своевольных казаков, частью их истребив. Но, не смотря на постигший их разгром, азовские и ордынские казаки не утратили своего значения и вскоре даже усилились, подстерегая на сакмах и бродах посольства и торговых людей. Их беспрестанные нападения вынудили султана, крымского хана, и великого князя отправлять свои посольства под сильным прикрытием от 100 и более воинов и идти без задержек в пути.
Так в 1505 г. Великий князь сообщал Менгли Гирею, чтобы тот не мешкал и высылал в Путивль свой сильный отряд для охраны «поминок» и послов, «ибо Путивль город пограничный, чтобы на поле о них не проведали, на поле же великий страх от казаков». После усиления военной охраны посольств, азовские казаки, лишённые лёгкой добычи, стали совершать набеги на русские украины, что вызвало нарекания и жалобы Москвы к мусульманским владыкам. В 1514 г. Великий князь просил турецкого посла Камала, бывшего в Москве, передать султану: «Если (султан) желает быть с нами в дружбе и любви братской, то пусть запретит азовским казакам, чтобы они украинам нашим ни какого зла не причиняли». Султан обещал пресечь разбои, но азовские казаки не слишком считались с его волей.
В следующем 1515 г. они по приглашению польского короля поступили на службу к великому князю Литовскому, недругу Москвы. Это известие вызвало раздражение Василия 3, который велел послу Коробову, едущему в Константинополь с посольством, в числе прочего сказать: «если султан хочет быть с царём в любви и дружбе, то пусть запретит казакам ходить из Азова и из Белгорода к литовскому нашему недругу на помощь, и на наём». На что в последствии, Коробову было сказано: «Те казаки ходили в Литовскую землю без салтанова ведома, а салтан того не ведает». На своём пути в Азов, Коробов увидел на Северском Донце, в близи устья речки Калитвы, казачий отряд, о чём и донёс Василию 3 отпиской: «а выше, государь, Донца видели есьмя перевоз, с Ногайская стороны, на Крымскую сторону перевозилися как бы человек с 100, а того, государь не ведаем, которые люди».
Кем были эти казаки сказать трудно. Е. Савельев полагал что это: « … были ни кто иные, как казаки запорожские или севрюки, двигавшиеся в то время на Дон». «Пока Москва была слаба, – писал Соловьёв – и всей Волгой, начиная от Казани, владели татары, движение казацких партий на Дон было незначительно, и казачество не могло ещё представлять в «Поле» правильно организованной силы для борьбы с мусульманством». Можно ли согласиться с этим утверждением? На первый взгляд всё логично и закономерно. Но у того же Савельева есть упоминание грамоты русского посла Голохвастого, который из Азова и Кафы сообщал великому князю Московскому Василию 3, что: «нагаи теснимые казаками, хотели перейти Волгу, но астраханский царь их не пустил».
Кто же тогда были эти казаки? Пришлые черкасы-запорожцы? Но тогда бы они ограничились ограблением нагаев и не преследовали их упорно и безжалостно, вытесняя за пределы Дона. Если это были казаки астраханские или казанские, то нагаи навряд ли бы стали уходить от своих притеснителей под сабли покровителей этих самых казаков – астраханского и казанского ханов. Тогда остаются только донские казаки, издревле обитавшие во временных городках полукочевым обычаем в дремучих лесах по Хопру, Медведице, Бузулуку и Верхнему Дону.
Судя по всему, это была не малочисленная ватага лихих удальцов, а весьма крупный казачий отряд, начавший выбивать с Дона своих старых врагов и конкурентов – нагаев. И очень скоро казакам удалось сбить со стойбищ многочисленные нагайские улусы. Вынудив их тем самым искать спасения в поволжских и прикубанских степях. Это предположение подтверждает российский историк 18 века Татищев, который в своей «Истории» писал, что Войско Донское было образованно в 1520 г., на 50 лет раньше, чем это принято считать. К сожалению, все исторические документы, на которые ссылался Татищев, были утрачены.
Однако в низовьях Дона ещё господствовали азовские казаки, беспрестанно тревожащие и разорявшие русские украины. Видя, что их нельзя унять силой оружия, Василий 3 обратился к Крымскому князю Аппаку, настроенному дружески к Москве с просьбой, предложить им служить ему, великому князю, за корма и жалованье. Аппак пошёл на встречу просьбе, и склонил было азовских и белгородских казаков перекочевать к Путивлю и служить России, но те вскоре изменили своё решение под давлением крымского хана, изменившего своё отношение к Москве. Он опасался её усиления. В результате чего татары прекратили междуусобную резню, подогреваемую Россией. Заключив союз и объединив силы, степняки стали готовиться к набегу в московские пределы.
В 1521 г. крымский хан Мухаммед Гирей заключил союз с казанским ханом Сахиб Гиреем и совершил опустошительный набег на Русь, угнав многие тысячи пленников. С этого времени отношения Москвы к донским казакам стало постепенно меняться и на степных удальцов, царь и бояре перестали смотреть только как на воров и разбойников, увидев в них зарождающийся щит России.
