Первая цель соответствовала обязательствам России перед «Священной лигой», антитурецким союзом Священной Римской империи (Австрии), Речи Посполитой (Польши) и Венеции, к которому Московское государство присоединилось при правительнице Софье.
В кампанию 1695 года Петр I избрал главным объектом операций турецкую крепость Азов, запиравшую выход из Дона в Азовское море. В походе 30-тысячную русскую армию сопровождал целый караван транспортных судов, в основном стругов. Однако взять крепость не удалось. Одной из причин этого явилась поддержка осажденных турецким флотом, под прикрытием которого Азов получал доставляемые морем боеприпасы и продовольствие.
Неудача первого азовского похода побудила Петра I предпринять срочные меры по строительству боевых кораблей. В начале 1696 года в подмосковном селе Преображенское и на верфи в Воронеже была развернута постройка кораблей и галер по европейским образцам. К их созданию привлекли иностранных мастеров и моряков, солдат Преображенского и Семеновского полков и 26 тысяч крепостных крестьян, назначенных согласно царскому указу.
Весной 1696 года были спущены на воду 2 корабля, 23 галеры, 4 брандера, 23 карбуса и шняка, а также 1217 грузовых стругов и 420 морских лодок. Вскоре вновь построенный «морской караван», как тогда называли флот, под командованием адмирала Ф.Я. Лефорта совершил первый поход вниз по Дону к стенам Азова.
Франц Яковлевич Лефорт (1655–1699 гг.) — первый главнокомандующий, адмирал российского флота, швейцарец на московской службе, мало понимал в морском деле, но был особо доверенным лицом и ближайшим советником молодого царя. Его авторитет придавал «морскому каравану» особое значение.
Ф.Я. Лефорт одновременно был и генералом армии, поэтому его иногда называли «генералом и адмиралом» или «генерал-адмиралом». Тогда же Петр I, по аналогии с иностранными флотами, назначил первых вице-адмирала, шаутбенахта (контр-адмирала) и капитанов кораблей. Следующие по старшинству корабельные офицеры именовались комендерами, поручиками, подпоручиками и констапелями. Все они, как и подавляющее большинство матросов, были иностранцами. Дополнялись экипажи кораблей солдатами гвардейских полков.
В походе участвовал только первый из двух построенных «воинских кораблей» 5-го ранга — 34-пушечный парусно-гребной фрегат (точнее, пинас) «Апостол Петр». Этот корабль длиной 32, шириной 7,36 и осадкой 2,7 м строил Август Мейер, который и стал его первым капитаном. «Апостол Петр» из-за мелководья не удалось вывести в Азовское море, но он принял участие в ближней блокаде и бомбардировке крепости. Зато в море прорвались казачьи лодки, а потом и галеры.