After playing football in her youth, Mutola started running. At age 15, she participated in the 1988 Seoul Olympics, but failed to qualify for the next round.
After finishing 4th in the 1991 World Championships final, her country put her hopes on Mutola for the first Olympic medal for the country in 1992. Although she did become Mozambique's first Olympic finalist, she placed 5th behind Ellen van Langen. At the same Games, Mutola ran her only 1500 m at an international championship, placing 9th in the final.
The next few years, Mutola dominated the 800 m event, winning the 1993 world title in Stuttgart. A favourite for the title in 1995 as well, she was disqualified in one of the heats. At the 1996 Olympics in Atlanta, Mutola won Mozambique's first Olympic medal, but not the gold medal, finishing third behind Cuba's Ana Quirot.
In 2000, in her fourth Olympics, Mutola finally won the gold. A medalist at the two previous World Championships, she beat her rivals in the final. She continued her successes in the 2001 season, grabbing the world title in Edmonton.