The story is told by Pushkin in the preface to his poem, The Bronze Horseman:

A wave-swept shore, remote, forlorn,

Here stood he, rapt in thought and drawn

To distant prospects…

This forlorn wave-swept shore was retaken by Peter in person from the Swedes during the Northern War. On May 12 (under the Gregorian calendar) 1703, the Russian tsar’s troops captured the Swedish fortress of Nyenskans (Nyenschantz) standing at the mouth of the Okhta River. And Peter decided that swampy banks of Neva overgrown with mosses are the right place for a window into Europe.

And he thought:

From here the Swede is ill-protected:

A city on this side, to thwart

His purposes, shall be erected.

Ground was broken immediately. On May 27 at the Zayachy Island in the widest place of the mouth of Neva, construction of a wood-and-earthwork fortress of “Sankt-Pieter-Burch,” that is, the fortress of St. Peter, began. A month later, a wooden temple of the Holy Apostles Peter and Paul was laid in an unfinished fortification. This prompted renaming of the fortress into Petropavlovsk, and its former name was given to the city instead.