27 ноября 1695 года был объявлен царский указ о Новом походе против турок и татар, после чего селе Преображенском под Москвой началось спешное строительство первых судов, которыми были брандеры и галеры[2]. Одновременно в Воронеже были заложены два 36-ти пушечных корабля «Апостол Петр» и «Апостол Павел». В Козлове, Добром, Сокольске и Воронеже приступили к постройке тысячи трехсот стругов, трехсот морских лодок и ста плотов[3]. В феврале 1696 года в селе Преображенском были заготовлены части для двух десятков галер, после чего они были доставлены в Воронеж, где к апрелю эти галеры были собраны. В частности, 2 апреля 1696 года в Воронеже были спущены на воду первые три галеры[4]. За тем последовали и остальные — двадцать.
В течение Пасхальной недели апреля 1696 года было спущено на воду еще несколько галер. Все они были построены в Воронеже на специально возведенных царем Петром Адмиралтейских верфях. «Воды реки Воронежа покрывались подходившими стругами, которые не только поспели к сроку все, но даже явились сверх наряда (плана — прим. авт.)» — писал историк Елагин[5].
23 апреля 1696 года начался длительный путь судов и их экипажей — первых русских военных моряков из Воронежа вниз по Дону. Помимо галер и стругов, то есть гребных судов, был спущен на воду и один из первых парусных боевых кораблей — «Апостол Петр», имевший у себя на борту тридцать шесть пушек. В итоге к Азову по Дону вышли восемь галер, четыре струга, четыре брандера и один корабль[6]. Потом к ним присоединилось еще четырнадцать галер и несколько стругов с провизией, боеприпасами, канатами, смолою, углем и другими припасами.
8 мая 1696 года вышел петровский «Указ по галерам», согласно которому экипажи судов должны были знать условные знаки, означающие соответствующие действия (первые флажные сигналы морского семафора). Помимо основных сухопутных сил и флотилии речных судов во втором Азовском походе приняли участие казаки на своих казачьих лодках. Именно с ними и шел Петр. Они следовали по притоку Дона — реке Каланче, впадающей в Азовское море. К концу мая практически все российские суда уже вошли в Азовское море.
Таким образом, созданный российский флот был готов встретить турецкие боевые суда, находившиеся в этом бассейне. Вместе с военной речной флотилией шли к Азову части российской армии, возглавляемой боярином А.С. Шеиным. Боярин Шеин был первым, в России военачальником, произведенным в генералиссимусы. Это произошло накануне данного похода согласно указу Петра I за проявленное полководческое мастерство в предыдущем Азовском походе. Надо заметить, что осуществить взятие Азова в 1695 году помешало не только отсутствие у российских сил боевых речных средств, а, прежде всего наличие таковых у турок. Теперь ничто не препятствовало российской победе.