The originally Roman Catholic parish church of Saint Nicholas was built in Altstadt south of Königsberg Castle in 1264 and then rebuilt from 1504 to 1537.

The Antonine monk Johann Amandus began preaching a Protestant sermon at the church in 1523, but was expelled the following year for being an agitating iconoclast.

Johannes Poliander became pastor in 1526 following the creation of the Duchy of Prussia and the parish's conversion to Lutheranism.

Because of the growing size of Altstadt's parish, Neurossgarten Church was constructed in the 1640s to the northwest.

After the dismantling of the original church, the parish converted the Altstädtischer Kirchenplatz into an enclosed garden; the developing square was renamed Kaiser-Wilhelm-Platz in 1897.