За строительством наблюдали сподвижники Петра I А. Д. Меншиков, Г. И. Головкин, Н. М. Зотов, Ю. Ю. Трубецкой, К. А. Нарышкин. Их именами были названы крепостные бастионы. Один из бастионов назван в честь Петра I Государевым.
Бастионы соединяются между собой стенами куртинами. Их, как и бастионов, шесть: Петровская, Невская, Екатерининская, Васильевская, Никольская, Кронверкская.
Сохранился чертеж, находившийся в коллекции Петра I. На нем изображен план Заячьего острова с намеченным на нем контуром крепости. Остров был небольшим длиной около 750 метров и шириной около 360 метров. Чтобы увеличить его размеры, были созданы искусственные насыпные участки.
Работы велись «с крайним поспешанием», так как шведы не теряли надежды вернуть утраченные земли. В течение лета 1703 года крепость была возведена из земли и дерева.
Первые строители крепости и города работали в тяжелых условиях. 10 апреля 1704 года Меншиков приказал коменданту крепости Р. В. Брюсу:
«1. Велеть ходить на работу как после полуночи 4 часа ударит или как из пушки выстрелят, а работать им до восьмого часа, а со восьми, ударив в барабан, велеть им отдыхать полчаса, не ходя в свои табары.
2. После того работать им до 11 часов, а как ударит, чтоб с работы шли и отдыхали два часа.
3. Как час после полудня ударит, тогда идтить им на работу, взяв с собою хлеба, и работать велеть до 4 часов после полуден, а 4 часа ударит, велеть им отдыхать полчаса с барабанным о том боем.
4. После того идтить им на работу и быть на той работе покамест из пушки выстрелено будет».
Голод, болезни, изнурительный ручной труд уносили тысячи жизней. По словам современника, «сооружение ее (крепости. Авт.) стоило множества народа при тогдашней необыкновенной дороговизне съестных припасов и недостатке в одежде, люди как мухи умирали от голода и холода и там же хоронились».
Строительство крепости велось во время боевых действий со шведами. Шведский генерал Майдель 24 июля 1704 года доносил в Стокгольм: «Петербург очень хорошо основан и укреплен, его положение таково, что он может стать одновременно сильной крепостью и процветающим торговым городом.
Если царь сохранит его в течение нескольких лет, то сила на море станет значительной».
В 1704 году, когда шведский отряд в 8000 человек и эскадра в составе 12 судов подошли к Петербургу и Кроншлоту, русские войска без особых потерь отбили противника. Был он отброшен со значительным уроном и на следующий год при попытке шведов снова овладеть городом и крепостью.
Однако земляная крепость не могла быть постоянным и надежным фортификационным сооружением. Когда Россия создала на Балтике свой флот, а граница на западе отодвинулась за Нарву, можно было, не опасаясь неожиданного нападения со стороны шведов, приступить к строительству более мощной, каменной крепости.
Перестройка Петропавловской крепости в каменную была начата 30 мая 1706 года и продолжалась с перерывами до 1740 года. Разрушение земляной крепости и возведение на новом свайном основании (под каменные стены крепости было забито около 40 000 свай) стен из кирпича и камня производились постепенно, на небольших участках, чтобы крепость не потеряла оборонительной способности. Южные бастионы были вынесены дальше в русло Невы.
На строительстве крепости преобладал ручной труд, но на более сложных работах гидротехнических применяли копры, водоливные машины с конной тягой и многое другое. Велись большие земляные работы. Их объем был равен почти 250 000 кубических метров. Газета «Ведомости» осенью 1703 года сообщала, что в крепости трудятся 20 000 подкопщиков. Строительные материалы подвозили на специальных судах. В 1709 году в распоряжении коменданта крепости Брюса было 205 таких судов и 7623 грузчика.
Исполнителем воли Петра I по строительству каменной крепости стал архитектор Доменико Трезини. Итальянец по происхождению, он родился в Швейцарии, несколько лет работал архитектором при дворе датского короля. В 1703 году Трезини, приняв предложение русского дипломата в Дании Измайлова, который по приказу Петра I отыскивал и приглашал на работу в Россию фортификаторов и архитекторов, приезжает в Петербург.
Трезини был первым архитектором молодой столицы. С 1706 года он приступил к «первейшей из главных работ» перестройке Петропавловской крепости в каменную и возведению на ее территории разнообразных построек, чему посвятил почти 30 лет своей жизни.
Крепость создавалась как первоклассное военно-инженерное сооружение XVIII века. Бастионы и куртины сложены из кирпича и камня. Их высота 1012 метров, ширина до 20 метров. Они состоят из двух стен: наружной (эскарповой) толщиной до 8 метров и внутренней (валганговой) толщиной 2 метра. Пространство между наружной и внутренней стенами в фасах бастионов (фасы стороны бастиона, обращенные к неприятелю) засыпали песком, щебнем, землей. Во фланках бастионов (фланки боковые стороны бастионов, соединяющие фасы с куртинами) устраивались казематы с амбразурами, предназначенными для установки орудий. Казематы в куртинах служили для хранения боеприпасов, вооружения, для размещения гарнизона.