Die „Große Freiheit“ zog im 17. Jahrhundert verschiedene Kirchen und Religionsgemeinschaften an, die in der Stadt Hamburg nicht geduldet wurden. Als dieses Viertel unter dänischer Herrschaft stand, durfte in dieser Straße der Glaube „frei“ ausgelebt werden.
Vor den Toren Hamburgs bauten 1675 mennonitische Glaubensflüchtlinge aus den Niederlanden in der Großen Freiheit 73/74 eine Holzkirche. Außerdem wurde 1678 in der Nähe (heute Paul-Roosen-Straße) ein gemeindeeigener Friedhof angelegt.
Nach dem Schwedenbrand 1713, dem auch die Mennonitenkirche zum Opfer gefallen war, errichtete die Gemeinde 1717 in zweiter Reihe an eben dieser Stelle eine Steinkirche, die fast 200 Jahre lang (bis 1915) als Versammlungsort diente. Vor der Kirche an der Straße wurden das Pfarrhaus und das Küsterhaus errichtet.
Als sich das Umfeld in ein Amüsierviertel wandelte, zogen die Mennoniten nach Altona-Nord, wo sich die Gemeinde bis heute in der Mennonitenstraße 20 trifft.
Die alte Kirche diente erst als Kriegsküche und später der Stadtmission Altona. Sie wurde im Zweiten Weltkrieg durch Fliegerbomben zerstört. Es gibt nur wenige Ansichtszeichnungen bzw. Fotos der ehemaligen Mennonitenkirche.
Im Jahr 2012 wurden im Rahmen stadtärchäologischer Bestandaufnahmen die Fundamente der alten Mennonitenkirche freigelegt und dokumentiert. Im Frühjahr und Sommer des Jahres 2015 wurde der Grundriss der ehemaligen Mennonitenkirche mit einem modernen mehrgeschossigen Wohnhaus überbaut.
Nur das ehemalige Küster- sowie das Pfarrhaus in der Großen Freiheit Nr. 73 und 75 blieben als inzwischen denkmalgeschützte Gebäude erhalten. Sie dienen als Wohnhäuser.
