Az első egyházmegyét I. Ottó császár alapította Magdeburgban 968-ban, érseki ranggal. Egyháztartományához a birodalom északkeleti egyházmegyéi tartoztak. A magdeburgi érsek a birodalom leghatalmasabb méltóságai közé tartozott, a 12. századtól fejedelmi címet viselt. A reformáció elsőként az érsekség területén bontakozott ki, a lakosság jelentős része protestáns vallásra tért át, több alkalommal az érseki székbe is protestáns személy került, a hivatal így elvesztette lényegét. 1580-ban a Magdeburgi főegyházmegyét végleg megszüntették, az érsek birtokait a brandenburgi őrgrófannektálta. A területen élő kislétszámú katolikus közösség csak diaszpórákban maradt fenn, központja idővel a magdeburgi Szent Sebestyén-templom lett.
Az egykori érsekség területe 1821-től a Paderborni egyházmegyéhez tartozott. A Paderborntól területileg is elkülönült magdeburgi diaszpórák vezetését 1834-től külön püspöki biztosra (Bischöflichen Commissarius) bízták. E hivatalt a Szent Sebestyén-templom prépostja töltötte be.
A második világháborút követően a sziléziai és szudétavidéki menekültek miatt jelentősen megnőtt a katolikusok létszáma Magdeburg környékén. A terület azonban Paderbornnal szemben a szovjet megszállási zónába került, így a pasztorációs feladatok ellátására segédpüspököt neveztek ki Magdeburgba. 1973-tól apostoli adminisztratúraként(Bischöfliches Amt) működött, továbbra is paderborni segédpüspök állt az élén, ám már mint apostoli kormányzó irányította, de facto önálló egyházmegyeként.
1994. június 27-én II. János Pál pápaCum gaudio kezdetű apostoli konstitúciójával egyházmegyei, a Szent Sebestyén-templomot pedig székesegyházi rangra emelte. Első püspökének az addigi kormányzót, Leo Nowakot nevezte ki, aki 2004-ig látta el hivatalát. Utóda segédpüspöke, Gerhard Feige.
Gerhard Feige
Az egyházmegye megalakulása óta a csökkenő hívőszám és a paphiány problémájával. Az utóbbi két évtizedben több mint 50 templomot zártak be az egyházmegyében. Feige ennek kezelésére 2010-re megreformálta az egyházszervezetet, plébániákat és espereskerületeket összevonva.
Egyházszervezet
Az egyházmegye területe 23 208km², határai lényegében egybeesnek Szász-Anhalt tartomány határaival. A 2010-es reform eredményeként jelenleg 8 espereskerületben 44 plébánia működik. A terület lakossága több mint két és félmillió, ebből hívők létszáma alig 82000 fő. 54 pap és 15 állandó diakónus áll az egyházmegye aktív szolgálatában.
