In den letzten Jahren wurde der Verein einer gründlichen Neustrukturierung unterworfen.
So beschloss der Magdeburger Stadtrat im Jahr 2004 den Abriss des Ernst-Grube-Stadions und den Neubau eines modernen Fußballstadions an gleicher Stelle – wodurch der FCM ab Februar 2005 gezwungen war, seine Heimspiele im kleineren Heinrich-Germer-Stadion auszutragen.
Die Mannschaft wurde in dieser Zeit kontinuierlich neu aufgebaut. Der Lohn waren der dritte Platz (2003/04) und der fünfte Platz (2004/05), bevor der FCM in der Saison 2005/06 als Oberliga-Meister erstmals nach dem Lizenzentzug in der Saison 2001/02 wieder in die Regionalliga aufstieg.
Mit einem 1:0-Sieg über den SV 09 Staßfurt wurde zum sechsten Mal der Landespokal nach Magdeburg geholt.
Abschlußtabelle
Verein | Sp | G | U | V | Tore | Diff. | Punkte | |
1. | 1. FC Magdeburg | 30 | 20 | 7 | 3 | 62:17 | +45 | 67 |
2. | VFC Plauen | 30 | 19 | 5 | 6 | 58:38 | +20 | 62 |
3. | FC Sachsen Leipzig | 30 | 17 | 5 | 8 | 47:21 | +26 | 56 |
4. | Hallescher FC | 30 | 14 | 11 | 5 | 46:26 | +20 | 53 |
5. | ZFC Meuselwitz | 30 | 15 | 8 | 7 | 52:40 | +12 | 53 |
6. | VfB Germania Halberstadt | 30 | 14 | 8 | 8 | 61:41 | +20 | 50 |
7. | Rot-Weiß Erfurt II (N) | 30 | 13 | 5 | 12 | 37:40 | –3 | 44 |
8. | FSV Budissa Bautzen (N) | 30 | 11 | 10 | 9 | 46:33 | +13 | 43 |
9. | Energie Cottbus II (W) | 30 | 10 | 10 | 10 | 44:43 | +1 | 40 |
10. | FV Dresden Nord | 30 | 7 | 15 | 8 | 41:36 | +5 | 36 |
11. | VfB Auerbach | 30 | 9 | 7 | 14 | 40:46 | –6 | 34 |
12. | FC Eilenburg | 30 | 7 | 10 | 13 | 32:39 | –7 | 31 |
13. | 30 | 7 | 3 | 20 | 29:59 | –30 | 24 | |
14. | TSV Völpke (N) | 30 | 6 | 6 | 18 | 25:75 | –50 | 24 |
15. | 30 | 5 | 8 | 17 | 30:51 | –21 | 23 | |
16. | 30 | 6 | 2 | 22 | 33:78 | –45 | 20 |
Legende | |
Aufsteiger in die Regionalliga | |
Teilnehmer an den Relegationsspielen um den Verbleib in der Oberliga | |
Absteiger in die Verbands- und Landesligen | |
(N) | Vorjahres-Aufsteiger aus den Verbands- und Landesligen |
(W) | Wechsel aus der Nord-Staffel |