Утверждению Татищева об образовании Войска Донского в 1520 г., казалось бы, противоречит государев наказ, данный в 1521 г. русскому послу в Турции Тредьяку Губину, из которого следует, что ни каких селений по Дону нет. Скорее всего, на Дону, в то время, действительно не было постоянных казачьих городков. Так как их сил не хватало для основания городков на большой реке, куда был доступ турецкого флота, взявшего в 1471 г. генуэзский город-крепость Азов. Обосновавшись на мелководных, а потому малодоступных притоках Дона, казаки совершали стремительные набеги на турок и татар ниже по течению и не давали им закрепиться на реке. Третьяк Губин, отправившись для переговоров в Константинополь, кроме всего прочего, должен был предложить туркам: « … как послам и гостям от обеих сторон по Дону бесстрашно ходить», и « … устроить России и Турции суда по Дону с военными людьми в нужном числе», с тем, чтобы турецкие суда плавали от Азова, а русские от украин до назначенной заставы на Дону, где посольства должны были пересаживаться для дальнейшего пути.

Первоначально местом обмена посольствами была предложена Переволока между Волгой и Доном, но рязанские городовые казаки, у которых просили совета по этому делу, заявили, что сходиться на Переволоке опасно из-за действий в этом районе астраханских татар и нагаев. Они предложили обмениваться послами на Медведице или лучше на Хопре, которые, судя по всему, контролировались донскими казаками. Однако этим планам не суждено было осуществиться из-за, совместного крымско-казанского похода на Россию, при активном участвии турецких янычар. Кроме того, утверждение Турции на Дону было крайне не выгодно для Москвы в подобных обстоятельствах.

Турецкий же султан заинтересовался этим предложением великого князя, так как оно давало возможность закрепиться на реке, не смотря на противодействие донских казаков. И вскоре в Москву был отправлен турецкий посол Скандер. На переговорах в Посольском приказе он передал согласие султана на обмен послами на Дону, и объявил, что Турция построит в месте обмена город и он, Скандер, на обратном пути в Константинополь, выберет место его закладки. Однако Москва, крайне недовольная турецкой экспансией на своих рубежах, не была в том заинтересована и отправила турецкого посла не Доном, а через Путивль, степью.

Здесь следует отметить, что в уже упомянутом набеге на Россию крымского хана Магмет Гирея и азовских турок султана Сулеймана, по приказу польского короля принимали участвие запорожские казаки гетмана Дашковича. Однако этот противоестественный союз продолжался не долго. Уже на следующий 1522 год черкасы гетмана Дашковича погромили крымские улусы, и Магмет Гирей жаловался на них польскому королю.

В последующие годы донские казаки усилили своё давление на нагаев, разоряя их улусы и отгоняя скот. Отношения между ними обострились до крайности, вызывая многочисленные жалобы нагайских властителей. В тоже время в 1523 г. активизировались азовские казаки, бесчинствовавшие в Подонье, грабившие купцов, посланников и русские украины. Обеспокоенный этим великий князь Василий Иванович, отправил с дворянином Иваном Морозовым грамоту турецкому султану с жалобой на этих воров и просьбой, указать азовскому паше, усмирить казаков: «Наши украинные люди ходять но украине, иные по своей воле, иных наместники посылают в поле для соглядания злых людей, а твои азовские казаки емлют наших людей на Поле, отводят в Азов и продают, окупы же берут с них великие, и вообще твои азовские, людям нашим много зла причинили».

В 1527 г. запорожские казаки, не смотря на союз польского короля с крымским ханом, соединившись с российскими казаками, совершили набег на крымские улусы, в то время когда хан со своей конницей ушёл в поход на Москву. Хан жаловался польскому королю: «Приходят к нам каневские и черкасские казаки, становятся под улусами нашими на Днепре и вред наносят нашим людям»; «Черкасские и каневкие властители пускают казаков вместе с казаками неприятеля твоего и моего (Московского князя) под наши улусы, и что только в нашем панстве узнают, дают знать в Москву».

В 1535 г. московское правительство отправило посольство к нагайскому князю Исламу, во главе с дворянином Наумовым и в сопровождении казаков. Но как только посольство вступило на нагайские земли, мурзы и уланы, натерпевшиеся много бед и лишений от казаков, ограбили его и подвергли избиению, а казаков хотели продать в рабство. Положение спасло вмешательство князя Ислама: «Приехали к Исламу твои казаки, и вот князья и уланы начали с них платье срывать, просят соболей; я послал сказать об этом Исламу, а князья и уланы пришли на Ислама с бранью; … и они все хотят казаков твоих продать». Конфликт, с трудом был улажен. В том же 1535 г. казаки сообщили в Москву о дворцовом перевороте в Казани: «В Москву приехали казаки, городецкие татары и сказывали, что к ним на остров приезжали казанские князья, мурзы и казаки, человек 60, объявили об убийстве царя Еналея и просили московского государя простить хана Шиг Алея, находящегося в русском плену, вернуть его из заточения с Белоозера и поставить его правителем Казани.

1537 г. Крымский хан Саип Гирей вновь жаловался польскому королю на казаков малороссийских, побивавших татар и состоящих в союзе с русскими казаками: «Приходят казаки Черкасские и Каневские, становятся под улусами нашими на Днепре и вред наносят нашим людям, я много раз посылал к вашей милости, чтоб вы их остановили, но вы их остановить не хотели; я шёл на московского (князя): 30 человек за болезнею вернулись от моего войска, казаки поранили их и коней побрали. Хорошо ли это: я иду на твоего непреятеля, а твои казаки из моего войска коней уводят? Я приязни братской и присяги сломать не хочу, но на те замки, Черкасы и Канев, хочу послать свою рать. А это знак ли доброй приязни братской? Черкасские и каневские властители пускают казаков с казаками непреятеля твоего и моего (великого князя московского), вместе с казаками путивльскими по Днепру, под наши улусы, и что только в вашем панстве узнают, дают весть в Москву; в Черкасах старосты ваши путивльских людей у себя держат; так как на Москву из, Черкас пришла весть за 15 дней перед нашим приходом». Но, не смотря на все меры, предпринимаемые польским королём, связь запорожцев с донцами и городовыми казаками не прерывалась.

В 1538 г. мурза приволжской орды нагаев Кель Магмет вновь жаловался малолетнему Ивану 4 на обиды и разорение, чинимые ему и его народу русскими казаками. На это последовала уклончивая отписка Посольского приказа и Боярской думы: «На Поле ходят казаки многие-казанцы, азовцы, крымцы и иные баловни казаки, а и с наших украин казаки с ними смешавшись ходят. И не люди, как нам, так и вам тати и разбойники, а на лихо их ни кто не учит: сделав какое лихо разъезжаются по своим землям».

***

В сороковых годах 16 века донские казаки резко усиливаются и окончательно вытесняют с Дона и его окрестностей нагаев, татар и казаков мусульман. Об этом можно судить из отписки в Москву в 1546 г. путивльского воеводы Михайлы Троекурова, доносившего, что на Дону появились из «разных украин» многие казаки из «черкасцев и киян», в том числе «твоих государевых». По всей видимости, донские казаки снеслись с запорожскими черкасами и, соединившись, очистили Дон по всему течению от татар и нагаев, установив полный контроль над всей рекой, вплоть до Азова. Казаки тюрки, до того беспрепятственно кочевавшие по Дону и окрестностям, и контролировавшие Подонье, по большей части были истреблены и рассеяны по степям. Вскоре совсем исчезли со страниц истории. Меж тем, утвердившись на реке, донские казаки стали устанавливать свои порядки, облагая данью проходящие мимо торговые караваны или попросту грабя их. В «крепких местах» появляются первые укреплённые казачьи городки, чьи обитатели с успехом отражали натиск степняков.

***

1548 г. После неудачного похода Ивана 4 на Казань, часть казаков бывших с ним в походе осело в украинных русских городах по Волге, « … дабы не допускать к Казани крымцов и нагаев, и кои после присоединения Казани и Астрахани, стояли на Волге, охраняя переправы большею частию у Переволоки и делая разъезды по степям для разведывания о предприятиях крымских». Так в 1548 г. посольство крымского хана к астраханскому царю (хану) Ямгурчею наткнулось на Дону, вблизи Переволоки на «острогу» – укреплённый деревянным тыном казачий городок. Все попытки татар взять «острогу» приступом были отражены её защитниками. По некоторым данным, это был городок атамана Михаила Черкашенина и мелкого путивльского помещика Истомы Извольского, одного из самых известных казачьих атаманов, решившего контролировать важнейший торговый путь. Крымский хан Сахиб Гирей послал для его уничтожения мурзу Елбузука, но тот был разбит и отступил.