В течение Пасхальной недели апреля 1696 года было спущено на воду еще несколько галер. Все они были построены в Воронеже на специально возведенных царем Петром Адмиралтейских верфях. «Воды реки Воронежа покрывались подходившими стругами, которые не только поспели к сроку все, но даже явились сверх наряда (плана — прим. авт.)» — писал историк Елагин[5].
23 апреля 1696 года начался длительный путь судов и их экипажей — первых русских военных моряков из Воронежа вниз по Дону. Помимо галер и стругов, то есть гребных судов, был спущен на воду и один из первых парусных боевых кораблей — «Апостол Петр», имевший у себя на борту тридцать шесть пушек. В итоге к Азову по Дону вышли восемь галер, четыре струга, четыре брандера и один корабль[6]. Потом к ним присоединилось еще четырнадцать галер и несколько стругов с провизией, боеприпасами, канатами, смолою, углем и другими припасами.
8 мая 1696 года вышел петровский «Указ по галерам», согласно которому экипажи судов должны были знать условные знаки, означающие соответствующие действия (первые флажные сигналы морского семафора). Помимо основных сухопутных сил и флотилии речных судов во втором Азовском походе приняли участие казаки на своих казачьих лодках. Именно с ними и шел Петр. Они следовали по притоку Дона — реке Каланче, впадающей в Азовское море. К концу мая практически все российские суда уже вошли в Азовское море.
Таким образом, созданный российский флот был готов встретить турецкие боевые суда, находившиеся в этом бассейне. Вместе с военной речной флотилией шли к Азову части российской армии, возглавляемой боярином А.С. Шеиным. Боярин Шеин был первым, в России военачальником, произведенным в генералиссимусы. Это произошло накануне данного похода согласно указу Петра I за проявленное полководческое мастерство в предыдущем Азовском походе. Надо заметить, что осуществить взятие Азова в 1695 году помешало не только отсутствие у российских сил боевых речных средств, а, прежде всего наличие таковых у турок. Теперь ничто не препятствовало российской победе.
Как упоминалось ранее 23 апреля (по новому стилю 3 мая) 1696 года из Воронежа к Азову вышел авангард галерной флотилии из восьми судов, которую возглавила галера «Принципиум» на которой был сам царь Петр, за которым проследовал отряд из остальных пятнадцати галер и четырех брандеров и 15 мая 1696 года эта флотилия прибыла в Черкасск[7]. Через два дня, 17 мая, произошло первое нападение отряда российских лодок на врага. Отряд состоял из казачьих лодок попытавшийся взять на абордаж два турецких корабля, но попытка оказалась неудачной, и казакам пришлось отступить. Но уже 20 мая 1696 года, отряду из сорока казачьих лодок удалось одержать победу над турецкой эскадрой под Азовым, в результате которой турки потеряли два корабля и десять тумбасов (грузовых судов)[8]. Согласно запискам Петра I утром выйдя в Азовское море, этот отряд обнаружил турецкую флотилию, на которой шла разгрузка грузов из тумбасов и атаковал вражескую флотилию[9].
В конце мая 1696 года российская флотилия пополнилась пятнадцатью галерами, пришедшими с Дона: Через несколько дней, 2 июня, подошли еще семь галер, 12 июня — галера и четыре брандера, после чего началась осада Азова с моря, создавшая преграду турецким судам в устье Дона, где он впадает в Азовское море. На суше действовала армия генералиссимуса Шеина, которая замкнула кольцо блокады у Азовской крепости. Видя, что российских судов больше, турецкой флот отступил в море, перестав оказывать помощь гарнизону крепости. В итоге 18 июля (28 июля по новому стилю) 1696 года Азов был взят.
После взятия Азова Петром I было выбрано место для гавани у мыса Таганий Рог, где и разместились суда принявшие участие в осаде крепости Азов. Позже там была основана крепость Таганрог. Надо отметить, что помимо боевых действий на Азовском море шли бои и на Днепре у турецкой крепости Тавань. Там тоже русские галеры и струги неоднократно атаковали турецкие речные средства. Они были построены в Брянске и проведены по реке Десне в Днепр. Флотилией командовал полковник Неплюев. Принимавшие участие в тех боях казаки, сражались у Аккермана и почти вплотную подошли к Очакову. Суда российской речной флотилии во время боевых действий защищали крепость Тавань взятую ранее русскими войсками под командованием боярина (в будущем ставшего генерал-фельдмаршалом) Б.П. Шереметьева, который вынудил отступить оттуда турецкие войска.