Ludwig Windthorst, jeden z ówczesnych wpływowych polityków chadeckich, apelował w swoim wystąpieniu z 29 grudnia 1887: Hamburg to brama Niemiec na świat. Niemcy, którzy tędy wyjeżdżają w świat, tu modlą się po raz ostatni na niemieckiej ziemi. Dlatego powinien on [kościół] nazywać się Mariacki – Stella Maris!(niem. oryg. Hamburg ist das Tor Deutschlands zur Welt. Die Deutschen, welche in die Welt hinausgehen, hier sprechen sie das letzte Gebet auf deutschem Boden. Deswegen soll sie Marienkirche heißen - Stella Maris! .
Architekt diecezjalny z Paderborn, Arnold Güldenpfennig, otrzymał w 1889 zlecenie budowy kościoła. Ówczesny biskup diecezji Osnabrücku Bernhard Höting chciał, aby kościół był zbudowany „w wywierającym spokojne i skromne wrażenie stylu romańskim.” Budowa kościoła trwała 4 lata. Kościół został zbudowany w stylu neoromańskim a jego zachodnia, dwuwieżowa fasada o wysokości 64 m nawiązywała stylem architektonicznym do katedry w Bremie; była ona na tyle wysoka, aby być widoczną z daleka.
28 czerwca 1893 roku gotowa budowla została poświęcona przez biskupa Hötinga i otrzymała wezwanie Najświętszej Marii Panny.