Между тем, к середине апреля 1703 года в районе Шлиссельбурга завершилось сосредоточение русских войск, предназначенных для овладения Ингрией. 23 апреля фельдмаршал Шереметев во главе 20-тысячного корпуса двинулся по правому берегу Невы брать Ниеншанц. Не доходя до Ниеншанца верст 15, Шереметев выслал вперед отряд из двух тысяч человек с целью произвести разведку боем. Отряд ночью атаковал 150 шведских драгун, стоявших вне крепости. Шведы бежали, но успели захватить двух пленных. Несколько русских даже залезли на крепостной вал. В принципе, этот отряд мог с ходу взять крепость; поскольку шведы растерялись, да и численность гарнизона не превышала 700 человек. Но командир русского отряда испугался и велел трубить отбой. 26 апреля к Ниеншанцу подошли основные силы Шереметева, были начаты осадные работы. После приведения в готовность осадных батарей Шереметев предложил шведскому коменданту капитулировать, но тот ответил, что «крепость вручена им от короля для обороны», и отказался сдать ее. 30 апреля началась бомбардировка крепости. К тому времени в лагерь осаждающих прибыл сам царь, именовавший себя бомбардирским капитаном Петром Михайловым. 1 мая шведский гарнизон сдался. Петр велел Ниеншанц переименовать в Шлотбург.
На следующий день (то есть 2 мая) разведчики доложили царю, что в Финском заливе замечена шведская эскадра. 5 мая два малых фрегата (галиота), шнява и большой бот стали на якорь в устье Невы. Петр приказал посадить в 30 больших лодок солдат Преображенского и Семеновского полков и отправился с ними вниз по Неве. Воспользовавшись темнотой и дождем, русские лодки внезапно вышли из-за островов невского устья и напали на два головных шведских судна.
Как вспоминал чуть позже сам Петр: «по нарочитом бою взяли два фрегата, один „Гедан“ о десяти, другой „Астрильд“ о восьми пушках а окон 14. Понеже неприятеля пардон зело поздно закричали, того для солдат унять трудно было, которые, ворвався, едва не всех покололи; только осталось 13 живых. Смею и то писать, что истинно с восемь лодок только в самом деле было».
Далее царь писал: «Хоть и недостойны, однако ж от господ фельдмаршала и адмирала мы с господином поручиком (Меншиковым) учинены кавалерами Святого Андрея».
По случаю взятия шведских судов Петр приказал выбить медаль с лаконичной надписью: «Не бывалое бывает». Такую медаль получили все участники операции:
После овладения Ниеншанцем все течение Невы, от истоков, где стоял Шлиссельбург, до устья, оказалось в руках русских. Тем не менее, Петр понимал, что рано или поздно шведы попытаются вернуть утраченные земли. Ключом к обладанию Ингрией для шведов был Нотебург, а для русских – Невское устье. Поэтому Петр решил сразу же закрепиться в устье Невы.
В «Гистории Северной войны» записано: «По взятии Канец (Так русские называли крепость Ниеншанц) отправлен воинский совет, тот ли шанец крепить, или иное место удобнее искать (понеже оный мал, далеко от моря, и место не гораздо крепко от натуры), в котором положено искать нового места (остров), где 16-й день мая (в неделю пятидесятницы) крепость заложена и именована Санкт-Петербург».
Собственно крепость начали строить на небольшом Заячьем острове (Иенчсаари) длиной 750 метров и шириной 360 метров. Остров имел важное стратегическое значение, поскольку находился у разветвления Невы на три рукава. Зато в инженерном отношении место было выбрано крайне неудачно. Плоский Заячий остров невысоко поднимался над уровнем Невы и при большом подъеме воды затоплялся. Таким образом, прежде чем строить крепость, остров нужно было «поднять». По приказу свирепого царя тысячи солдат и принудительно согнанных местных жителей таскали землю на Заячий остров. Изнурительная работа и плохое питание привели к большой смертности строителей. Петропавловская крепость, да и весь Санкт-Петербург, не только в переносном, но и в буквальном смысле, построены на костях десятков тысяч мужиков и солдат.
Проект крепости составлял лично царь с помощью французского военного инженера Жозефа Ламберта. Немец Гюйсен, очевидец сооружения Петропавловской крепости, оставивший подробное описание Петербурга и Кроншлота в первые годы их существования, писал, что крепость построили «непостижимо скоро». В короткий срок – за полтора месяца – были засыпаны землей стены крепости, укреплены бастионы (раскаты), выступавшие за общую линию крепостных стен. Шесть бастионов, намного увеличивавшие площадь обстрела вокруг крепости, были названы в честь соратников Петра I – Меншикова, Нарышкина, Трубецкого, Головкина, Зотова. Один бастион был назван Царским или Государевым раскатом. К осени на бастионах уже стояли более 120 пушек. Позже, начиная с 30 мая 1706 года, земляные бастионы стали заменять каменными. В крепости возвели деревянную церковь во имя Петра и Павла, Рядом с церковью построили деревянный дом для царя (19х6,5 метров), с двумя комнатами, сенями и кухней, с холстинными выбеленными обоями, с простой мебелью и кроватью. Дом Петра в таком виде сохранился по сей день.