Muthemba was a pivotal player in Mozambique’s independence war. She was born into a prominent nationalist family and became involved in the struggle at an early age, first in secret student groups before joining the Mozambique Liberation Front (FRELIMO) in 1960.
She was the driving force behind the Women’s Detachment Movement, which is now known as the ‘Organization of Mozambican Women,’ a group of women who took up arms to fight for the independence of their country. She married Samora Machel, the man who would become Mozambique’s first president, when she was 24 years old.