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