Nachdem sich im Zuge der Industrialisierung wieder Katholiken, überwiegend aus dem Eichsfeld und aus Oberschlesien, im evangelisch geprägten Sudenburg angesiedelt hatten, erfolgte 1861 die Gründung des Missionspfarrei Sudenburg. Die Gottesdienste fanden zunächst in einer katholischen Schule statt. Zuvor gehörten die Katholiken in Sudenburg zur Pfarrgemeinde Magdeburg.
Am 13. Mai 1867 wurde an der Morgenstraße, der heutigen Rottersdorfer Straße, der Grundstein für den Kirchenbau gelegt. Damals waren von den etwa 6.500 Einwohnern Sudenburgs rund 1.000 katholisch. Bereits am 8. Dezember des gleichen Jahres folgte die Kirchweihe. Im gleichen Jahr wurde Sudenburg nach Magdeburg eingemeindet. 1892 wurde eine vom Orgelbauer Wilhelm Rühlmann für 5046 Mark hergestellte Orgel eingebaut. 1897 erfolgte die Erhebung zur eigenständigen Pfarrei. In den Jahren 1944 und 1945 wurde die Kirche durch Kriegseinwirkung erheblich beschädigt, und die Orgel unbrauchbar. 1949 bekam die Kirche eine Orgel mit pneumatischer Traktur. Diese bestand großteils aus der ausgelagerten Orgel der St. Katharinen-Kirche Egeln, welche man mit reparierten Teilen der kriegszerstörten Orgel von St. Marien ergänzte. 1983 bestellte die Gemeinde bei Hermann Eule Orgelbau eine neue, doch gab es bei Orgeln Wartezeiten von bis zu 14 Jahren, da die DDR-Orgelbaufirmen vorrangig mit devisenbringenden Exportaufträgen beschäftigt waren. Zungenstimmen und ein geräuscharmer Gebläsemotor waren in der DDR nicht zu bekommen und wurden bereits 1984 von westdeutschen kirchlichen Stellen spendiert. Erst 1993 konnte die Gemeinde die zusammengebastelte Orgel von 1949 durch das neue Eule-Werk mit 19 Registern und 1330 Pfeifen ersetzen. Es war 1983 mit 120.000 DDR-Mark veranschlagt, letztendlich kostete es 360.000 D-Mark.
Am 28. Oktober 2007 wurde der für beiden Kirchengemeinden Ottersleben und Sudenburg umfassende Gemeindeverbund Magdeburg-Süd gegründet und im November 2010 zur heutigen Pfarrei St. Maria zusammengeführt.
