Дворянская конница старинного строя в 120 тыс. человек была послана под начальством Б.П.Шереметева в крымском направлении, к низовьям реки Днепра, где стояли турецкие укрепления. Но главное направление для удара было иным. Другая армия направлялась к устью Дона, против крупнейшей турецкой крепости Азов, запиравшей выход к Азовскому морю. При этом один отряд под начальством генерала Гордона, ■численностью свыше 9 тыс. человек, с артиллерией и сна-рвдами, пошел сухим путем на юг от Москвы через Коломну и Тамбов. Но главное войско в 10 тыс. человек во главе с генералами Лефортом и Головиным отправилось к Азову водой. На Москве-реке у Каменного моста было приготовлено множество «стругов» для перевозки войск, артиллерии Я чрипасов.
Отплыли 28 апреля 1695 г. Караван судов двигался медленно. У Коломны Москва-река впадает в реку Оку, и здесь суда задержались на два дня из-за сильного ветра. 6 мая прошли Рязань и только 16 мая пришли к Нижнему, где Ока впадает в Волгу. В этом войске находился Петр I. Под Царицыном Волга всего ближе подходит к Дону. Здесь войска должны были высадиться и идти сушей к Дону. Переход через степь к Дону был очень тяжел. Обозных лошадей не хватало, пушки и снаряды перетаскивалась людьми. Достигнув Дона у городка Паншина, стояли четыре дня, так как снова грузились на суда, чтобы плыть Доном.
25 июня приплыли к центру донских казаков, к городу Черкасску, где остались на три дня. Наконец, 29 июня пристали к берегу близ Азова. Отряд генерала Гордона, прибывший прежде, приветствовал подошедшие войска и Петра салютом из всех пушек и мушкетов. В тот же день состоялся военный совет. Весь путь от Москвы до Азова занял два месяца, с 28 апреля до 29 июня.
Турецкая крепость Азов была расположена в устье Дона, в 15 километрах от Азовского моря. Она была обнесена каменными стенами, земляным валом и рвом. В трех километрах от крепости вверх по Дону на обоих его берегах стояли «каланчи» — две каменные башни, укрепленные пушками. Русские войска приступили к осаде Азова.
В русском войске не было единого руководства: генералы спорили между собой, а Петр, которому было только 23 года, еще не брал на себя общего командования. Голландский матрос, состоявший на русской службе, перебежал к туркам и сообщил им, что русские во время зноя беспечно спят. Турки сделали вылазку в это время дня, перебили много спящих и увезли 6 орудий. В середине июля русские полки захватили обе каланчи, построенные турками выше Азова. После этого туркам было предложено сдать крепость на выгодных условиях. Но те ответили отказом. Тогда 5 августа был произведен штурм Азова. Три отряда, по 1500 человек в каждом, с разных сторон бросились на крепость. Казаки на 20 лодках спустились по Дону в море и сделали попытку полностью окружить крепость. Но русские отряды действовали во время штурма несогласованно, а турки упорно сопротивлялись, и штурм закончился ничем. После этого были усилены осадные работы, стали рыть траншеи и вести подкоп под крепость.
Неопытный минер неудачно заложил мину в подкоп, и от взрыва пострадали не турки, а русские, было много раненых и убитых. На 25 сентября был назначен второй цпурм Азова. Взрывом была пробита брешь в крепостных укреплениях Азова, но турки отбили все атаки, и второй штурм также окончился неудачей. Осенняя непогода не позволила продолжать осаду, и командование решило прекратить затянувшиеся военные действия.
1 октября 1695 г. осада была снята и начался отход войск на север, только у каланчей были оставлены русские отряды. Обратно шли сушей по степи, где трудно было найти воду и корм, к тому же наступили морозы. Австрийский посол, сопровождавший русскую армию, писал об отходе русских войск: «По дороге я видел, какие большие потери понесла армия во время своего марша, хотя и не будучи преследуема никаким неприятелем; нельзя было без слез видеть, как по всей степи на протяжении 800 верст лежали трупы людей и лошадей, наполовину объеденные волками» . Удачнее были операции другого войска, действовавшего под началом Б.П.Шереметева вместе с украинскими казаками в низовьях Днепра. Ему удалось захватить четыре небольшие турецкие крепости. Однако неудача под Азовом заставила отказаться от широких замыслов.