Nach dem Wachsen der östlichen Wilhelmstadt wurde 1935 für den neugebildeten Pfarrbezirk Paulus-Ost eines der ersten kirchlichen Großbauten der Zwischenkriegsjahre geschaffen. Die Aufbrüche des „Bauhauses“ und des für Magdeburg typischen „Neuen Bauens“ sind darin erkennbar, aber teilweise bereits den rückwärtsgewandten Architekturvorgaben der 1930er Jahre gewichen. Der Entwurf stammt von Architekt Georg Heinze, der auch dem Gemeindekirchenrat angehörte. Die Anlage war ein 3-flügliger Gebäudekomplex: im Osten das auf einer Ost-West-Achse ausgerichtete Kirchengebäude, im Westen das Pfarrhaus (kriegszerstört), dazwischen als Verbindung ein Flachbau, der den Kindergarten der Gemeinde und Verwaltungsräume beherbergte. Im Norden sollte dem Gebäude ein großer Innenhof angefügt werden, der kriegsbedingt nicht mehr zur Ausführung kam.

Im Kirchengebäude, das vier Aufgänge hatte, befand sich einen Kirchsaal mit 800 Plätzen, eine Theaterbühne und eine architektonisch interessante, nicht mehr existierende hölzerne Bauhaus-Kassettendecke. In ihm ist heute das landeskirchliche Archiv untergebracht. Ein Kunststeinrelief an der Südfront zeigt eine „deutsche Familie“ und das Bibelzitat „Ich und mein Haus wollen dem Herrn dienen“, in das ursprünglich ein Hakenkreuz eingefügt war. Der erste Pfarrer prägte die sich dort versammelnde Gemeinde als „Deutscher Christ“ entsprechend der Ideologie des Nationalsozialismus. 2015 hat die Gemeinde diese unheimlichen ersten zwanzig Jahre ihrer Geschichte in einer Ausstellung aufgearbeitet und dokumentiert (pdf). 1955 wurde der Pfarrbezirk Paulus-Ost zur eigenständigen Matthäusgemeinde. Inzwischen ist sie Teil des Kirchspiels Magdeburg-West mit der Paulusgemeinde im Zentrum. Nach vielen baulich mühseligen Jahren aufgrund der Kriegsschäden und während der DDR-Zeit erfolgte Anfang der 2000er Jahre ein grundlegender Umbau zum heute sichtbaren Bestand.

Dir Kirchengemeinde ist dankbar für ihre helle und freundliche Wohnstatt. Den Kirchsaal ziert das ursprüngliche große Altarkreuz. Durch die variable Bestuhlung bietet er viele Möglichkeiten für gottesdienstliche und andere Nutzung. Das holzgeschnitzte Lesepult zeigt mit der Darstellung der Christusbegegnung des Apostels Paulus vor Damaskus die ursprüngliche und heute wieder lebendige Verbindung mit der Paulusgemeinde. Ihm entspricht eine sehr geschmackvoll gestaltete hölzerne Taufstätte. Der Kirchenmusik stehen eine zweimanualige Orgel und ein Flügel zur Verfügung.