Перестройка Петропавловской крепости в каменную была начата 30 мая 1706 года и продолжалась с перерывами до 1740 года. Разрушение земляной крепости и возведение на новом свайном основании (под каменные стены крепости было забито около 40 000 свай) стен из кирпича и камня производились постепенно, на небольших участках, чтобы крепость не потеряла оборонительной способности. Южные бастионы были вынесены дальше в русло Невы.
На строительстве крепости преобладал ручной труд, но на более сложных работах — гидротехнических — применяли копры, водоливные машины с конной тягой и многое другое. Велись большие земляные работы. Их объем был равен почти 250 000 кубических метров. Газета «Ведомости» осенью 1703 года сообщала, что в крепости трудятся 20 000 подкопщиков. Строительные материалы подвозили на специальных судах. В 1709 году в распоряжении коменданта крепости Брюса было 205 таких судов и 7623 грузчика.
Исполнителем воли Петра I по строительству каменной крепости стал архитектор Доменико Трезини. Итальянец по происхождению, он родился в Швейцарии, несколько лет работал архитектором при дворе датского короля. В 1703 году Трезини, приняв предложение русского дипломата в Дании Измайлова, который по приказу Петра I отыскивал и приглашал на работу в Россию фортификаторов и архитекторов, приезжает в Петербург.
Трезини был первым архитектором молодой столицы. С 1706 года он приступил к «первейшей из главных работ» — перестройке Петропавловской крепости в каменную и возведению на ее территории разнообразных построек, чему посвятил почти 30 лет своей жизни.
Крепость создавалась как первоклассное военно-инженерное сооружение XVIII века. Бастионы и куртины сложены из кирпича и камня. Их высота 10―12 метров, ширина — до 20 метров. Они состоят из двух стен: наружной (эскарповой) толщиной до 8 метров и внутренней (валганговой) толщиной 2 метра. Пространство между наружной и внутренней стенами в фасах бастионов (фасы — стороны бастиона, обращенные к неприятелю) засыпали песком, щебнем, землей. Во фланках бастионов (фланки — боковые стороны бастионов, соединяющие фасы с куртинами) устраивались казематы с амбразурами, предназначенными для установки орудий. Казематы в куртинах служили для хранения боеприпасов, вооружения, для размещения гарнизона.
С юго-востока крепость была неприступна благодаря полноводной Неве, с севера ее предохраняли пролив и дополнительные сооружения — земляной кронверк и кавальер.
Кронверк (вспомогательное укрепление из одного бастиона и двух полубастионов, соединенных куртинами) предназначался для прикрытия и поддержки артиллерийским огнем значительной части крепостной стены. Построен в 1705―1708 годах. Его земляные валы к августу 1708 года уже были одеты дерном. На них стояло 78 орудий. Валы были окружены рвом с водой. Кавальер (вспомогательное сооружение внутри бастиона; служил для обстрела местности перед крепостью) был сооружен на территории бастиона Головкина.
Вдоль острова был вырыт канал длиной 400 и шириной 5 метров. По нему подвозили строительные материалы. В 1882 году канал засыпали.
В 30―40-е годы XVIII века началось возведение каменных равелинов (равелин — вспомогательное сооружение, расположенное впереди куртины и между двумя бастионами); они прикрывали крепостные ворота и куртины от огня артиллерии.
С восточной стороны крепости был построен Иоанновский равелин, названный в честь старшего брата Петра I Ивана Алексеевича. Он прикрывал бастионы Государев, Меншикова, Петровскую куртину и Петровские ворота. С западной стороны крепости — Алексеевский равелин, названный в честь отца Петра I царя Алексея Михайловича. Равелин прикрывал бастионы Трубецкой, Зотова, Васильевскую куртину и Васильевские ворота.
Равелины отделялись от территории крепости рвами с водой. Через рвы были перекинуты подъемные мосты. В конце XIX века рвы засыпали.
Строительные работы в крепости велись и позже.
С течением времени кирпичные стены от непогоды стали разрушаться. В 70―80-е годы XVIII века стены крепости со стороны Невы на протяжении 700 метров были облицованы гранитом. С тех пор гранитные стены крепости с взлетающим ввысь золотым шпилем Петропавловского собора стали частью величественного архитектурного ансамбля, возникшего на берегах Невы.
Большое значение для судьбы крепости и молодого города имели победы русской армии над шведами под Полтавой в 1709 году и под Выборгом в 1710 году. Полтавская победа, по словам Петра I, явилась «камнем в основании Санкт-Петербурга», а взятием Выборга была «крепкая подушка в изголовье Санкт-Петербурга положена».