Отец Марии — железнодорожный служащий, а мать — продавец на рынке.
В детстве Мария хорошо играла в футбол, причём она играла вместе с мальчиками, так как команд девочек не было. Бегом Мария стала заниматься только в 1988 году под руководством Стелиу Кравейринья — сына знаменитого мозамбикского поэта Жозе Кравейриньи, который сам был большим поклонником спорта. Не привыкшая к регулярным тренировкам Мария была не в восторге от бега, но тренер убедил её продолжить занятия, так как успел разглядеть в Мутоле большой потенциал. Уже через несколько месяцев после начала тренировок Мария выиграла серебро на дистанции 800 м на чемпионате Африки 1988 года. В том же году в возрасте 15 лет Мутола дебютировала на Олимпийских играх в 1988 году в Сеуле, где установила в предварительном забеге личный рекорд 2 мин 4,36 сек, но финишировала последней и не пробилась в финал.
В 1990 году 17-летняя Мутола побеждает на чемпионате Африки в Каире на 800 и 1500 м, а на следующий год сенсационно становится 4-й на чемпионате мира в Токио на 800-метровке, попутно установив мировой рекорд среди юниоров.
Жозе Кравейринья помог организовать спортивную стипендию для Марии: с помощью программы солидарности МОК она получила возможность поехать в Соединённые Штаты для обучения и стажировки. В качестве принимающей школы была выбрана средняя школа Спрингфилда в Орегоне — Мутола не говорила по-английски, а там был португалоязычный сотрудник.
В 1992 году на Олимпиаде в Барселоне Мозамбик уже ждал от Марии своей первой медали в олимпийской истории, но она осталась только пятой на 800 м. Кроме того, единственный раз в карьере на Олимпиаде Мутола бежала и 1500 м, но заняла лишь 9-е место. В 1992 года на Играх в Барселоне на дистанции 400 метров выступала и двоюродная сестра Марии Тина Паулино, но не сумела пробиться в финальный забег.
Олимпийская медаль была завоёвана через 4 года в Атланте, но она была лишь бронзовой (чемпионкой стала россиянка Светлана Мастеркова). Для трёхкратной к тому времени чемпионки мира Мутолы, которая не проиграла ни одного старта на 800 м с 1992 года, это было неудачей. Тем не менее Мутола принесла Мозамбику первую олимпийскую медаль в истории. Там же, в Атланте, Мария была удостоена чести нести флаг Мозамбика на церемонии открытия Олимпиады.
После долгожданной победы на Олимпиаде-2000 Марию встречали в Мозамбике как национальную героиню, а в её честь была названа одна из улиц столицы Мозамбика Мапуту.
Семь раз (1993—1995, 1998, 2000—2001 и 2003) Мутола была обладательницей лучшего результата сезона в мире в беге на 800 м. Никому, кроме Марии, не удавалось показывать лучший результат сезона в мире на этой дистанции больше 5 раз за карьеру — ни среди женщин, ни среди мужчин. У женщин трижды быстрейшей в сезоне была россиянка Светлана Мастеркова (1991, 1996 и 1999), а у мужчин лучшее достижение на счету Уилсона Кипкетера — пять раз (1995—1997, 1999, 2002).