Da den første kirke blev for lille, besluttede biskop Theodor Suhr i 1968 at bede arkitekt Johan Otto von Spreckelsen om at udføre tegninger til en ny Skt. Nikolaj Kirke. Kirken blev indviet og taget i brug d. 16. november 1969.
Det er en rustik, kvadratisk bygning, opført i gasbeton. Skt. Nikolaj Kirke blev det første eksempel på den kube- og kvadratform, arkitekten havde tegnet sig frem til omkring nytår 1968. Det er den første bygning i den arkitektur, der også genkendes i ’Menneskehedens Triumfbue’, opført i Paris i 1983.
Den indre kube i Skt. Nikolaj Kirke, med et sidemål på 8,5 meter, er næsten samme størrelse som det allerhelligste i Salomons Tempel (Eze. 40,3-5).
