В апреле 1696 г. армия и флот под командованием Петра I двинулись из Воронежа к Азову. Одновременно в низовья Днепра выступило войско Б. П. Шереметева. На него возлагалась задача — отвлечь на себя силы крымских татар и овладеть турецкой крепостью Очаков. На Дону и Днепре также действовали отряды донских и запорожских казаков.
19 мая 1696 г. русский флот вышел в устье Дона. В это время на рейде стояла турецкая флотилия из 13 кораблей. Для доставки гарнизону Азова боевых и продовольственных припасов от флотилии к крепости направилось 13 тунбасов (груженных судов) в сопровождении 11 ушкалов (суда охранения). На подступах к крепости у Каланчинского устья русский флот атаковал неприятеля, захватив 10 тунбасов с порохом, ядрами, гранатами, сукном и продовольствием. Воодушевленные успехом, казаки под командованием Фрола Минаева на стругах вышли в море против турецкой флотилии. Потеряв два корабля, турецкие моряки поспешили поднять паруса и обратились в бегство.
В конце мая — начале июня русский флот блокировал Азов с моря. Появление 14 июня турецкой эскадры из 6 кораблей и 17 галер с десантом 4 тыс. человек, присланных в помощь азовскому гарнизону, не повлияло на дальнейший ход боевых действий русского флота. Простояв две недели на рейде в бездействии, турецкая эскадра, так и не осмелившись приблизиться к Азову, ушла в море.
28 мая — 3 июня на суше русская армия подошла к Азову и заняла сохранившиеся с прошлого года осадные сооружения. 17 июня прибыли украинские казаки (Черниговского, Гадячского, Лубенского, Прилукского и двух охотницких полков — всего около 15 тыс. человек) под командованием наказного гетмана Якова Лизогуба. На них возлагалась задача — отражать степные набеги татарских войск и охранять армию с тыла. К тому же казаки принимали участие в отражении вылазок из крепости и в строительстве осадных сооружений.
Артиллерийский обстрел Азова в течение двух недель не дал заметных результатов. Учитывая опыт взятия Кизикермена, русское командование решило соорудить на подступах к крепости два земляных вала. Для выполнения этой титанической работы ежедневно назначалось до 15 тыс. человек. Первый вал, превышавший крепостной, подходил к одной из башен Азова и прикрывал наступающие войска от вражеского обстрела. Второй — пониже — предназначался для установки артиллерии.
Решающие дни в борьбе за Азов наступили в середине июля. Артиллерийским огнем удалось разрушить одну из башен крепости. Украинские и донские казаки под прикрытием земляного вала подошли к башне, захватили ее и несколько часов отбивали атаки врага. Успех казаков стал прологом решающего штурма Азова, начавшегося 18 июля. Жестокая битва продолжалась до полудня. Во второй половине дня турецкий гарнизон начал переговоры о капитуляции. 19 июля русские войска и казацкие полки вступили в Азов. Первую победу в борьбе России за выходы к южным морям обеспечили совместные действия русской армии, казацких полков и вновь созданного флота.
Военные действия в низовьях Днепра велись в меньших масштабах. Русские войска и украинские казацкие полки, расположившись у рек Берестовой и Орчик, не допускали вторжения татарских отрядов в южные украинские земли.
Значительные силы Крымского ханства и турецкого флота отвлекались от помощи Азову морскими и сухопутными походами запорожцев. 21 мая 1696 г. 500 запорожцев во главе с атаманом Чалым захватили на Черном море девять судов с различными товарами и доставили их в Запорожскую Сечь. В июле того же года запорожцы на чайках снова вышли в Черное море, достигнув Крымского побережья у Евпатории. На обратном пути казаки, избегая столкновения с турецкой флотилией, высадились на берег Днепра, соорудили укрепленный лагерь и несколько дней отбивали атаки крымских татар и турецких янычар. Однако силы были неравными. Часть казаков попала в турецкий плен и была отправлена в Очаков.
Другой отряд запорожцев во главе с Яковом Морозом, Григорием Сагайдачным и Петром Сорочинским, выйдя на 40 чайках в Черное море, поджег три вражеских корабля и захватил важные письма из Турции крымскому хану. Не рискуя вступать в стычку с турецкими кораблями в устье Днепра, казаки высадились на берег, дошли до Таванска, оттуда вскоре прибыли в Запорожскую Сечь.
Не меньший успех имели и действия запорожцев на суше. В июне 1696 г. несколько сот запорожцев во главе с кошевым атаманом Иваном Гусаком разбили татарский отряд. При этом были получены от пленного ценные сведения о планах вражеского командования.