Во второй трети XVI века параллельно процессу образования централизованного Московского государства на обширном пространстве причерноморских степей – «Диком поле», шло формирование военно-политического сообщества, которое в дальнейшем получит название Войска Донского.
Вплоть до сегодняшнего дня вопрос о происхождении донского казачества и его формировании как специфического этносоциального явления Русского государства остается дискуссионным. Сами казаки в поэтической «Повести об Азовском осадном сидении» свое появление в низовьях Дона связывали с поиском вольности и бегством от всяческих притеснений в центральных областях Русского государства, вызванных процессами усиления государственного гнета.
"Отбегаем мы ис того государьства Московского из работы вечныя, ис холопства неволнаго, от бояр и от дворян государевых…" Повесть об Азовском осадном сидении донских казаков
В письменных источниках донские казаки в первый раз упоминаются в 1549 году в грамоте Ивана IV Грозного ногайскому князю Юсуфе, в которой сообщалось, что русский царь «велел казакам своим путимльским и донским улусы воевати и недружбу царю (крымскому хану) делать». В середине XVI века казаки представляли собой уже настолько внушительную военную силу, что для борьбы с ними союзников стал искать султан могущественной Османской империи – Сулейман I Великолепный.
Со второй половины XVI века донцы принимали активное участие во всех крупных военных столкновениях Московского царства: отряды донских казаков участвовали в покорении Казанского и Астраханского ханств, в сражениях изнурительной Ливонской войны 1558–1583 годов, в освоении Сибири, оказывали отпор набегам крымских татар. На протяжении XVI века закладывались основы будущей противоречивой политики русского правительства по отношению к вольному казачеству, которое, с одной стороны, боролось с бегством русского населения в Дикое поле, а с другой – стремилось заручиться поддержкой казаков в борьбе с многочисленными врагами, поставив их на сторожевую и военную службу русскому царю.
Первое из сохранившихся актов признания Московским царством донского казачества в качестве самостоятельной военной и политической силы зафиксировала царская грамота от 3 января 1570 года, направленная Иваном Грозным донским казакам на Северский Донец вместе с дипломатической миссией И. П. Новосильцева к султану Оттоманской Порты.
В условиях продолжавшейся Ливонской войны Московское царство было вынуждено искать примирения с турками. В грамотах, которые русский посол вез султану, говорилось о традициях долгой московско-турецкой «дружбы», восходящей ко временам Ивана III. Казаки, терроризировавшие турецкие берега в Азовском море, были названы «лихим людьми», которые «ссору чинили» между Москвой и Портой.
Несмотря на нелицеприятные отзывы о казаках в переговорах с турками, Иван Грозный нуждался в военной поддержке усиливающегося донского казачества. Учитывая военные заслуги казаков, их активное участие в войнах Русского государства, Иван IV предложил им царскую службу – сопровождение русского посольства до Азова «безо всякого ослушания», а взамен отмечал: «мы вас за вашу службу жаловати хотим». С тех пор донцы деньгами, хлебом, вином, порохом, пушечными ядрами стали получать «государево жалованье», что позволило им в дальнейшем совершать частые набеги на турецкий Азов и Крым.
Появление царской грамоты 3 января 1570 года рассматривается как особая веха в истории Войска Донского и даже считается началом официальной истории донского казачества. Однако, начиная служить русскому царю, донские казаки продолжали сохранять свою военно-политическую самостоятельность и независимость от московской власти, выстраивая отношения с ней по принципу взаимовыгодного сотрудничества.