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

Вопреки всем трудностям, уже через пять месяцев стали вырисовываться очертания крепости. Она строилась в форме вытянутого шестиугольника с шестью мощными бастионами, каждый из которых возводился под личным надзором одного из ближайших сподвижников Петра и был назван по его имени: Меншиков, Головкин, Зотов, Трубецкой и Нарышкин. Строительством шестого бастиона руководил сам Петр, и он назван в его честь. Первоначально укрепления строились из земли и дерева, затем Петр приказал возвести вместо земляных валов высокие и толстые каменные стены. Сурово и грозно поднялись они над Невой на тридцать футов, ощетинившись рядами орудий. Незадолго до конца царствования Петра ганноверский посланник Христиан Фридрих Вебер отметил: «На одном из бастионов они, по примеру датчан, каждый день поднимают крепостной штандарт на высокой мачте… По праздникам же они поднимают другой, большой желтый флаг с двуглавым орлом, держащим в когтях четыре моря, омывающих границы России – Белое, Черное, Каспийское и Балтийское».

Неподалеку от крепости находился маленький, пятьдесят пять футов в длину и двадцать футов в ширину, одноэтажный бревенчатый домик, в котором царь останавливался, пока велись работы. Он был выстроен солдатами 24–26 мая 1703 года. В доме три комнаты – спальня, столовая и кабинет. Нет ни печей, ни дымоходов, поскольку царь жил там только летом. Примечательно, какую изобретательность проявил Петр, чтобы бревенчатая хижина походила на европейский домик. Слюдяные окна были большие, с переплетами на голландский манер, кровельный гонт на островерхой крыше уложен и покрашен так, что создавал видимость черепицы, а обтесанные бревенчатые стены раскрашены под кирпичную кладку. (Домик – старейшее строение в городе – был для сохранности заключен в кирпичный футляр и уцелел до наших дней.)

Работы по возведению крепости шли «с крайним поспешанием», поскольку Петр постоянно опасался возвращения шведов. И действительно, их отряды появлялись каждое лето. В 1703 году, когда не прошло и месяца с тех пор, как Петр занял дельту Невы, с севера подступил шведский отряд в 4000 человек и встал лагерем у реки Сестры. 7 июля 7-тысячный русский отряд под командованием самого Петра, состоявший из четырех драгунских и двух пехотных полков, выступил против шведов, разбил их и вынудил отступить. Петр постоянно находился под вражеским огнем, и наблюдавший это Паткуль был вынужден напомнить своему высокому покровителю, что «он тоже смертен, и одна мушкетная пуля может вывести из строя всю армию и ввергнуть страну в пучину опасности». Тем же летом шведский адмирал Нуммерс держал на якоре в устье Невы девять кораблей, блокируя выход в море и поджидая случая подняться вверх по реке и помешать строительству русских укреплений. Петр тем временем вернулся на верфи на Ладожском озере, чтобы ускорить строительство кораблей. В результате на рейде новой невской твердыни появилось множество судов, в том числе и фрегат «Штандарт». Не имея достаточных сил, чтобы бросить вызов более мощной эскадре Нуммерса, корабли не выходили в море, пока холода не вынудили Нуммерса увести свой флот. Тогда Петр на «Штандарте» вышел в Финский залив.