Niên thiếu
Mutola sinh năm 1972 tại thị trấn Chamanculo tồi tàn ở ngoại ô Maputo, sau đó được gọi là Lourenço Marques, thủ đô của Mozambique Bồ Đào Nha. Cha cô được làm việc trong ngành đường sắt và mẹ cô là một người bán hàng ở chợ. Khi còn là một cô gái trẻ, cô đã tỏ ra xuất sắc trong bóng đá. Cô chơi với các cậu bé khác, vì không có giải đấu hay đội nào cho con gái. Năm 1988, khi chỉ mới 15 tuổi, cô được khuyến khích tham gia môn điền kinh bởi một trong những nhân vật văn học hàng đầu của Mozambique, nhà thơ Jose Craveirinha, một người hâm mộ thể thao cuồng nhiệt. Con trai ông, Stelio, bản thân là một người giữ kỷ lục nhảy xa quốc gia, từng thi đấu tại Thế vận hội Mùa hè 1980, là huấn luyện viên đầu tiên của Mutola. Không quen với việc đào tạo chuyên sâu, Mutola ban đầu quyết định rằng việc chạy bộ không dành cho cô, nhưng được thuyết phục để tiếp tục khi rõ ràng là cô có tiềm năng to lớn.