Dobrá rada blízkého spolupracovníka Petra Velikého byla patrně jedním z impulzů, který přiměl ruského cara v roce 1703 k budování Petropavlovské pevnosti. S myšlenkou vytvořit na břehu Něvy u Finského zálivu vojenskou základnu s přístavem, skladišti na zboží a armádní výzbrojí přišel za panovníkem hrabě Fjodor Golovin – zkušený generál a první ruský kancléř. Osud a výsledky obratné válečnické politiky daly Petrovi jedinečnou příležitost, kterou bez váhání využil.
Při obhlídce bažinatých břehů narazil car na Zaječí ostrov, který mu svým tvarem připomněl válečný koráb rozrážející vodní hladinu. Bylo rozhodnuto. Na místě dlouhém 750 a širokém 400 metrů se mimořádně dařilo rychlonohým ušákům – odtud jeho název. Dnes původní obyvatele ostrova připomíná socha zajíce vedle mostu při vstupu do pevnosti.
Podle legendy prý car uviděl, jak nad ostrovem krouží orel – symbol carské moci. Přikázal tedy připlout se člunem ke břehu. Když vystoupil na pevninu, pokácel nejbližší borovici a vytvořil z ní kříž. Ten zabodl do země se slovy: „Tady bude stát pevnost.“ Současně s hradbami se na ostrově začal budovat i kostel a vstupní brána do pevnosti. Původní obranný val zhotovený podle nákresů samého cara začal první architekt Petrohradu, Švýcar Domenico Trezzini, nahrazovat hradbami z kamenů a cihel. V roce 1712 pak na místě dřevěného chrámu začal budovat monumentální stavbu zasvěcenou sv. Petrovi a Pavlovi. Podle svatostánku se pak začalo říkat celé pevnosti – Petropavlovská. Její jméno Sankt-Peterburg přešlo s původně německou výslovností na město, které se začalo rodit na březích Něvy.
I když Trezzini postavil například též budovu Dvanácti kolegií (carských ministerstev) na Univerzitním nábřeží, kde v současnosti sídlí Petrohradská státní univerzita, jeho nejvýznamnějším dílem je právě chrám v Petropavlovské pevnosti. Představuje ukázkový příklad Trezziniho neopakovatelného architektonického stylu označovaného jako petrovské baroko. Chrám byl dokončen až v roce 1733, tedy po smrti velikého cara, který za svého života mohl spatřit jen zvonici s vysokou pozlacenou špičkou. Původní dřevěná byla v 19. století rozebrána a nahrazena vyšší kovovou. Celá věž se sochou anděla na vrcholku tak v současnosti měří úctyhodných 122,5 m a je nejvyšší stavbou v Petrohradu. Kostel s bohatě zdobenými interiéry měl v minulosti kromě náboženské i další funkci – sloužil jako pohřebiště všech ruských panovníků a panovnic od Petra Velikého až po předposledního cara Alexandra III. V později přistavěné velkoknížecí hrobce byli pochováváni další rodinní příslušníci Romanovců. Těm však představitelé sovětské vládnoucí moci nepopřáli klid ani po smrti. Po revoluci byly veškeré ostatky odvezeny a velkoknížecí hrobka se využívala jako depozitář a muzejní sál.
V roce 1704 se na protilehlém břehu řeky začala stavět základna námořnictva – Admiralita. Obrazně i fakticky tak Petr I. překonal Něvu, a položil základ bouřlivému rozvoji budoucí metropole. Lokalita určená pro stavbu korábů nebyla vybrána náhodou. Řeka byla v tomto místě dostatečně široká, což umožňovalo pohodlné spouštění plavidel na hladinu. Navíc mohla Admiralita posloužit při případném napadení jako další obranná pevnost. Při první přestavbě komplexu v roce 1719 vznikla i charakteristická věž, na jejímž vrcholku najdeme unikátní detailně propracovaný koráb, který se stal symbolem města. Současná budova se 407 metrů dlouhým průčelím je v pořadí třetí na stejném místě. Právě k věži, kterou Petrohraďané příznačně překřtili na „jehlu“, se váže řada pozoruhodných historek. Jedna z nich například tvrdí, že ve věži je ukrytá nádoba se zlatými mincemi, jiná zase hovoří o tom, že je ve věži schovaný kompas Petra Velikého.