Азовский поход 1695 года окончательно убедил Петра I в том, что без наличия флота ему не овладеть даже сравнительно слабой приморской крепостью. Центром кораблестроения стал город Воронеж. Здесь на верфи в 15 верстах от впадения реки Воронеж в Дон в апреле 1696 года был спущен на воду 36-пушечный парусно-гребной фрегат "Апостол Петр".
Корабль строился по чертежам и при участии "искусного мастера галерных строений" датчанина Августа (Густава) Мейера, ставшего впоследствии командиром второго такого же 36-пушечного корабля "Апостол Павел".
Длина фрегата 34,4 м, ширина 7,6 м. Корабль был плоскодонным. Борта в верхней части корпуса заваливались внутрь, что затрудняло абордаж. Шканцы открытые, на срезанном баке оставались площадки для размещения абордажной команды. Корабль имел три мачты со стеньгами и бушприт с вертикальным утлегарем. Фоковую и гротовую парусность составляли нижние паруса и марсели. На бизань-мачте была только бизань. Кроме того, имелось 15 пар весел на случай безветрия и для маневра. "Апостол Петр" 14 лет довольно успешно служил в составе Азовского флота.
В 1712 году после неудачного Прутского похода Азовский флот прекратил свое существование. Судьба же корабля "Апостол Петр" неизвестна, хотя Петр I дал указание "сохранить его вечно в пример за первенство".