Правда, большинство историков считает, что Петр не присутствовал при закладке крепости и города, он лишь утвердил выбор места для крепости и уехал – скорее всего, на Олонецкую верфь. Но, как известно, у преданий свои, порой причудливые, сюжеты. Согласно одному из них, то место, где течет «большая река Нева, очень понравилось царю батюшке Петру. И он решил на берегах реки построить город, а реку в гранит одеть. Он собрал люд работящий, стал молиться Богу, а потом вскочил на коня и крикнул: «Богово и мое!» и перелетел Неву. Второй раз крикнул: «Богово и мое!» и опять перепрыгнул Неву. В третий раз крикнул царь: «Мое и Богово!»… и не долетел – упал вместе с конем в воду. Народ же гудел и радовался. Царь вышел из воды, снял свой треух, поклонился на все четыре стороны и объявил: “Люд православный! Прежде Богово, а потом уж наше! Начнем! С Богом!”»

После освящения места для храма царь Петр подал знак к началу земляных работ. Когда первый ров достиг двух аршин глубины, в него был опущен высеченный из камня ящик, в который Петр поставил золотой ковчег с частицей мощей апостола Андрея Первозванного, считающегося небесным покровителем России.

Первоначально укрепления крепости были земляными. Дело в том, что крепость XVIII в. не похожа на крепости Средневековья. Башни и каменные стены оказались бессильны против артиллерии, и на смену им пришли земляные валы, в которых с шипением увязали каменные и чугунные пушечные ядра. Крепость приобрела форму звезды, лучи которой образуют пятиугольные площадки – бастионы.

Бастионная система была рассчитана таким образом, что, в какой бы точке ни атаковал противник крепость, он всегда попадает под огонь ее пушек либо с фланга, либо с тыла.

Тем не менее в 1706 г. земляные укрепления начали заменять каменными. Строительство крепостных бастионов и куртин велось под руководством архитектора и инженера, «полковника фортификации» Д. Трезини. Этот талантливый зодчий, почти 30 лет руководивший перестройкой крепости в камне, многое сделал для Петербурга. Однако, уже будучи в преклонном возрасте, перечень своих трудов он неизменно начинал фразой: «Первейшей из главных работ – Санкт-Петербургская фортификация, которая застроена каменным зданием с 1706 г.»

По проекту Трезини к фланкам бастионов северных полигонов главного вала крепости были пристроены орильоны, служившие защитой для амбразур боевых казематов. Кроме того, архитектор также являлся автором проекта устройства оборонительных и охранительных казематов в бастионах и куртинах крепости.

С целью усиления главного вала крепости ее план в 1708–1709 годах был скорректирован, на северном берегу узкого пролива, отделяющего Заячий остров от Березового, возведен кронверк – еще одно дополнительное сооружение в виде бастиона и двух полубастионов.

Последний раз план крепости был дополнен в 1731–1740 гг., когда по проекту немецкого военного инженера Б.-Х. Миниха были построены два каменных равелина, названные западным – Алексеевским в честь царя Алексея Михайловича; и восточным – Иоанновским в честь царя Иоанна Алексеевича. Другие бастионы еще ранее получили имена А. Д. Меншикова, Г. И. Головкина, H. М. Зотова, Ю. Ю. Трубецкого и К. А. Нарышкина. Юго-западный бастион назван Государевым; куртины, обращенные к Неве, названы Невской и Монетной (которая в конце XVIII века была переименована в Екатерининскую), восточная и западная куртины – Никольской и Кронверкской.

Во всех этих бастионах и куртинах помещения перекрыты цилиндрическими, крестовыми или сомкнутыми сводами и объединены сквозными проходами.

В 1740 г. работы по перестройке крепости в камне были завершены. В 1752 г. по проекту инженера В. Сипятина к шпицам бастионов были пристроены вместо первоначальных деревянных каменные аппарели для подъема пушек и боеприпасов.

В 1779–1786 гг. эскарповые стены крепостной ограды, обращенные к Неве, по проекту инженера Р. Р. Томилина и под руководством инженера Ф. В. Бауэра были облицованы серым гранитом, в результате чего фасады южных полигонов крепости были органично включены в панораму невских берегов, одетых в гранит, и приобрели вид, соответствующий парадному центру города.

Работы по облицовке закончились в 1787 г. сооружением гранитных Невских ворот. На фасадах бастионов укреплены памятные доски с указанием даты окончания облицовки (Екатерининский бастион – 1780 г., бастион Петра – 1783 г.).

Таким образом, Петропавловская крепость приобрела форму сплюснутой шестиконечной звезды, в центре которой возвышался шпиль Петропавловского собора. Сформировался целостный архитектурный ансамбль, ядром которого стал собор, находящийся в пространственной взаимосвязи с триумфальными Петровскими воротами.

Эти каменные ворота в виде триумфальной арки, служащие для въезда в Петропавловскую крепость с восточной ее стороны, были построены по проекту Трезини в 1717–1718 гг. Первоначально на месте каменных стояли деревянные ворота, украшенные большим барельефом, изображавшим низвержение Симона-волхва апостолом Петром. Барельеф этот сохранился и был перенесен на каменные ворота. В 1722 г. над аркой установили отлитого из свинца и вызолоченного двуглавого орла.

Поверхность фасадной стены ворот обработана рустами. Стена первого яруса прорезана по сторонам проезда глубокими нишами, в которых установлены статуи: Беллоны – богини войны; и Минервы – покровительницы ремесел, наук и искусств.