Петр решил поехать к донским казакам, осмотреть Азовское море с ними и там устроиться прочно, оттуда завести торговлю с чужими землями.
16 марта 1695 года донской атаман Фрол Минаев получил от царя тайную грамоту. Царь сообщал ему, что в Тамбове соберется царское войско под начальством наемного немецкого генерала Гордона и отправится на реку Хопер, а с Хопра на Дон, в Черкасск. Войску Донскому царь приказывал тайно изготовиться для завоевания Азова. Царь напоминал атаману Фролу Минаеву, чтобы указ его оставался тайной и никто, кроме атамана и войсковых старшин, о нем ничего не знал, и чтобы войско собралось тихо и о приходе русских полков на Дон в Азове «прежде времени не уведали».
Одновременно с этим старые московские войска, огромное конное войско, под начальством боярина Шереметьева пошло на Днепр, чтобы воевать против турок вместе с малороссийскими казаками.
На Дон пошли новые, обученные Петром по немецким уставам, полки: Преображенский, Семеновский, Бутырский и Лефортов, шли московские стрельцы, городовые солдаты и царские слуги. Всего шла 31 тысяча человек. Войсками командовали воеводы, названные уже по-иностранному генералами: Головин, Лефорт и Гордон. При войске был сам царь, принявший на себя звание командира артиллерийской роты и называвший себя «бомбардир Петр Алексеев».
Армия эта шла сначала на судах по Волге до Царицына. От Царицына сухим путем прошли до городка Паншина на Дону. За этот путь молодые солдаты царя Петра сильно устали. Им, утомленным долгой греблей на судах на Волге, пришлось весь этот путь на руках тащить тяжелые пушки. В Паншине не хватило запасов. Молодому войску царскому пришлось поголодать.
От Паншина по Дону пошли на казачьих стругах.
Первый раз Московский царь появился на Дону. Первый раз увидал он приволье Задонья и крутой правый берег, покрытый лесистыми балками. Все занимало молодого царя. Он долго беседовал с казаками-гребцами, слушал их песни, любовался их уменьем стрелять. Во время ночлега в Верхне-Курмоярской станице царь остановился у казачки Чебачихи. Но не сиделось ему в душной избе. Он вышел на берег Дона и любовался привольной степью. Заметив на другом берегу утку, царь приказал ее застрелить одному из сопровождавших его молодых московских людей. Тот выстрелил и промахнулся. Царь спросил: «Нет ли казака, который мог бы это сделать». Вызвался молодой казак Пядух. Он взял свою пищаль и, не целясь, на вскидку убил утку.
- Исполать, казак, - сказал ему государь. - Хотя и я убью, но только поцелюсь!
26 июня 1695 г. царь Петр прибыл в Черкасск. Здесь войска отдыхали три дня. 29 июня русское войско, подкрепленное 7000 казаков атамана Фрола Минаева, подошло к Азову.
Но, как ни тайно собиралось под Азов царское войско, турки узнали об этом. 6 июня они получили подкрепление и большой запас. Без кораблей царское войско не могло подойти к Азову. Турки устроили по обоим берегам Дона башни - каланчи, прочно построенные и снабженные артиллерией. Между каланчами были забиты по Дону сваи и протянуты цепи. Не взявши каланчей, нельзя было подойти и к Азову.
Кликнули клич охотникам из донских казаков и обещали по 10 рублей каждому охотнику. Донцы вместе с одним из гвардейских полков окружили одну из башен; артиллерия ядрами своими снесла, вершину ее и часть стены. На рассвете 14 июня двести казаков, вызвавшихся на приступ охотою, вскочили в каланчу, расположенную на левом берегу реки. На другой день турки сделали вылазку, напали на пехотную дивизию генерала Гордона, находившуюся в середине русской позиции, во время полуденного отдыха захватили у русских 7 орудий, загвоздили большую часть остальных и перебили, и переранили около тысячи сонных молодых русских солдат. Но на другой день казаки отомстили за русских и заняли и вторую каланчу.
Русские войска начали теснее облегать крепость. После жаркого дела Петр устроил сильный окоп, или, как тогда называли, шанец на правом берегу Дона и вооружил его пушками и мортирами.
К августу осадные валы наши подошли к самым азовским стенам, и на 5-е августа был назначен штурм крепости. Но турки отбили этот штурм, и наши войска потеряли полторы тысячи человек. Подорвать крепостные стены порохом, как то сделали в 1637 году казаки, не пришлось. Только к 25 сентября Гордону удалось взорвать мину и разрушить городские стены на протяжении 20 саженей. Войска ворвались в город, но русские полки, не привыкшие сражаться на улицах с турками, наступавшими с необыкновенной пылкостью, были откинуты, и Гордон приказал отступить.
Как раз в это время атаман фрол Минаев с 1000 донцов на каюках, а за ним посаженные на лодки полки гвардии: Преображенский и Семеновский, под начальством Апраксина, подошли к Азову с моря, овладели укреплениями и тоже ворвались в город; но их не поддержали, и они принуждены были отступить… Здесь донские казаки явились учителями морского дела молодых потешных полков Петра.