В это же время союзники России по Священной лиге Австрия и Польша настойчиво требовали от русского правительства активизации военных действий в Причерноморье. К этому призывала Петра и голландская дипломатия, рассчитывая облегчить положение своего союзника по Аугсбурской коалиции — Австрии.
Все эти соображения и обстоятельства побудили Петра к решительным действиям. При подготовке к летней кампании 1695 г. было решено нанести удар не по вассалу Турции — крымскому хану, а непосредственно по туркам, их крепости Азову. Этот план принципиально отличался от задач крымских походов, носивших в целом лишь отвлекающий характер. Взятие Азова резко ухудшило бы позиции Османской империи в Причерноморье, что, возможно, сказалось бы на исходе всей войны. Кроме военных аспектов при выборе момента и направления борьбы против Турции учитывалась и международная обстановка. Русские представители в Риме и в Варшаве сообщили о возможности одностороннего выхода из войны Австрии и Польши, что развязало бы руки Турции для вторжения на Левобережную Украину и южные области России. Военный же успех России, как полагал Петр, устранил бы эту опасность и способствовал бы укреплению единства антитурецкой коалиции.
Весной 1695 г. русская армия двинулась под Азов. Но овладеть турецкой крепостью в кампании этого года не удалось. Отсутствие флота лишало возможности блокировать Азов с моря, что позволяло туркам беспрепятственно доставлять в крепость подкрепление, боеприпасы и продовольствие. В результате турецкому гарнизону удалось отбить все атаки русских войск. Убедившись в бесперспективности дальнейших боевых действий, Петр принял решение снять осаду и отвести армию в глубь страны.
Неудача под Азовом не привела Петра в уныние и не заставила его отказаться от своих замыслов. Напротив, вскрыв причины провала кампании 1695 г., царь со свойственной ему энергией приступил к подготовке нового азовского похода, в котором важная роль отводилась флоту. Для его строительства на верфях Воронежа было собрано 25 тысяч крестьян и работных людей, которые под непосредственным руководством Петра в небывало короткий срок спустили на воду 2 корабля, 23 морские галеры и несколько десятков мелких судов. Учитывая пагубные последствия того, что под Азовом не было инженеров, царь приказывает вызвать из Австрии и Пруссии специалистов по взятию крепостей.
В начале мая сосредоточенная в Воронеже армия и военный флот двинулись на юг. В конце месяца войска заняли под стенами Азова прошлогодние траншеи и начали обстрел крепости из пушек. 16 июня русская артиллерия разрушила важную часть крепостных сооружений, и Петр отдал приказ о подготовке к генеральному штурму. Однако ход событий на море ускорил развязку. Подошедший на помощь Азову турецкий флот с подкреплениями, боеприпасами и продовольствием не смог прорваться к крепости, так как устье Дона было блокировано русской галерной флотилией. Не дождавшись наступления русских галер, турки подняли паруса и ушли в море. Это и решило судьбу крепости. Исчерпав все средства обороны, гарнизон Азова 18 июля выбросил белый флаг.
Взятие Азова значительно укрепило военно-стратегические позиции России и Причерноморья и существенно повысило ее международный престиж. Прямым результатом этого явилось заключение в феврале 1697 г. нового антитурецкого союза в составе России, Австрии и Венеции.
Овладев Азовом, Россия, однако, не получила свободного доступа в Черное море. Предстояла нелегкая и длительная борьба за Керчь и право пользоваться проливами, соединяющими Черное море со Средиземным. Для решения этой задачи было необходимо продолжать войну с Турцией как на море, так и на суше, но уже с привлечением более крупных сил армии и флота.
В связи с этим Боярская дума в ноябре 1696 г. по предложению Петра приняла решение о сооружении флота из 52 крупных кораблей. Однако казна не располагала суммами, чтобы финансировать столь грандиозное по своим масштабам мероприятие. Поэтому для строительства флота были созданы компании — «кумпанства» из светских и духовных феодалов, которые, естественно, переложили бремя новых расходов на своих крепостных крестьян. Одновременно было принято постановление о заселении Азова и мобилизации трудового населения на сооружение гавани в Таганроге.
Начало строительства флота со всей остротой поставило вопрос о мастерах и морских офицерах, которых в России не было. И Петр находит необычайно смелое решение данной проблемы — послать за границу молодых дворян для изучения морского дела.