In gioventù Maria Mutola eccelle nel calcio, tanto che dopo una visita in Portogallo le viene proposto di trasferirsi a Lisbona per allenarsi nel Benfica, ma viene di fatto impedita dal governo mozambicano. Nel 1988 debutta, a soli 15 anni, nel mondo dell'atletica leggera internazionale: partecipa nello stesso anno ai Campionati africani, vincendo un argento, prima di prendere parte ai Giochi olimpici di Seul, dove però viene eliminata al primo turno, giungendo ultima con il tempo di 2'04"36 (suo nuovo primato personale).
Nonostante la sua vittoria ai Campionati africani del 1990, Mutola non riesce a migliorarsi cronometricamente: una certa opposizione interna al Paese le impedisce di allenarsi in modo adeguato, se non nei periodi precedenti ai grandi appuntamenti. Nel 1991 si lascia alle spalle tutto questo grazie all'International Olympic Committee Solidarity Program che le permette di partire per gli Stati Uniti d'America per studiare e allenarsi alla Springfield High School. Sorprende molti arrivando quarta nella finale dei Mondiali di Tokyo, stabilendo il nuovo record mondiale juniores con il tempo di 1'57"63.
Ai Giochi olimpici del 1992 a Barcellona ci sono grandi aspettative, intorno all'atleta, per la possibile prima medaglia olimpica del Mozambico. Finisce però quinta in una gara vinta dall'olandese Ellen van Langen. Durante quest'edizione dei Giochi corse, per la prima e ultima volta in un evento internazionale, i 1500 m piani, gara in cui fu nona. A fine stagione vince la Coppa del mondo ed è l'unica atleta che riesce a battere Ellen van Langen durante tutto l'anno.
1993-1995: i primi titoli mondiali
Negli anni seguenti Mutola domina la scena mondiale e nel 1993 vince sia i Mondiali indoor che quelli all'aperto. Favorita ai Mondiali 1995 viene squalificata in semifinale per invasione di corsia. Una piccola consolazione arriva al Memorial Van Damme qualche settimana dopo, quando batte il record mondiale dei 1000 m piani, diventando la prima donna a correre la distanza in meno di due minuti e mezzo. Supera il record anche nella specialità indoor della stessa distanza.
Grande merito del suo successo è dovuto alla sua allenatrice Margo Jennings, che la segue dai tempi della Springfield High School, e che continua a seguirla anche quando la Mutola si trasferisce a Johannesburg per scappare dall'alto tasso di polline presente nell'aria. Jennings, che ha allenato altre campionesse come Kelly Holmes, Agnes Samaria e Tina Paulino, faxava a Mutola i programmi di allenamento in Sudafrica.
1996: la delusione olimpica
Ai Giochi olimpici del 1996 ad Atlanta Mutola è nuovamente la grande favorita, dal momento che viene da 40 vittorie consecutive fra 800 e 1000 m piani. Sofferente a causa della febbre conclude la prova solo terza dietro a Svetlana Masterkova ed Ana Fidelia Quirot. Nello stesso anno la Masterkova le strappa il record mondiale dei 1000 m piani.
Successivamente Mutola conquista il bronzo ai Mondiali del 1997 e l'argento nel 1999. Vince anche i Mondiali indoor, a distanza di sole due settimane dalla morte del padre in un incidente stradale. Vince due volte i Giochi del Commonwealth e per quattro volte rappresenta l'Africa in Coppa del mondo.
2000: la conquista dell'oro olimpico
Il suo momento migliore arriva però ai Giochi olimpici del 2000 a Sydney, quando Mutola conquista finalmente anche l'oro olimpico, sconfiggendo le due principali rivali Stephanie Graf e Kelly Holmes. Al suo ritorno in Mozambico, dove le fu intitolata una strada di Maputo, viene accolta in trionfo.
Continua i suoi successi con l'oro ai Mondiali 2001 di Edmonton e a quelli del 2003 di Saint-Denis. Sempre nel 2003, vincendo al Memorial van Damme, si aggiudica la Golden League, portandosi a casa da sola tutto il milione di dollari del jackpot in palio.
Le ultime stagioni ed il ritiro
Nel tentativo di diventare la prima donna a difendere con successo l'oro olimpico negli 800 m, Mutola partecipa ai Giochi olimpici del 2004, finendo quarta e fuori dalla zona medaglie. Sofferente ad un tendine del ginocchio è in corsa fino all'ultimo per la vittoria, che va però a Kelly Holmes.
Ai Giochi olimpici del 2008 di Pechino, arriva nuovamente in una finale concludendo però quinta, in una gara dominata dalla keniota Pamela Jelimo, che aveva precedentemente battuto il record africano degli 800 m piani della Mutola. A fine stagione decide di ritirarsi dall'attività agonistica, terminando così una lunghissima carriera sportiva.
Record nazionali
Maria Mutola, in testa al gruppo, durante la vittoriosa finale dei Giochi olimpici di Sydney 2000.
Seniores
200 metri piani: 23"86 (Langenthal, 20 luglio 1994)
.svg){kind=small}
.svg){kind=small}
