Muzenda was born in the Gutu District of what was then the Victoria Rrovince of Southern Rhodesia, firmly under British colonial rule, as a son of a peasant farmer, and brought up by his grandmother, who ensured his regular attendance of a local Catholic missionary school. A relatively bright child, he was sent for teacher training after spending his teenage years herding the family's cattle, and, following the advice of his tutor, travelled to the Marianhill mission in Natal, South Africa, where he showed a proficiency in carpentry.
Between completing his carpentry course and furthering his studies, Muzenda became aware of politics during contacts with fellow students, which included several men prominent in black activism South Africa and Rhodesia; after his return to Rhodesia in 1950, he worked in a furniture factory in Bulawayo and became involved with Benjamin Burombo, an activist who was among the earliest to challenge discriminatory laws.
After marrying his wife Maud, a nurse, Muzenda moved to the Midlands town of Umvuma in 1955 and started his own carpentry business; he also stayed active in political activism and eventually become administrative secretary of the Zimbabwe African National Union (ZANU), attracting the attention of Rhodesian security forces and being imprisoned in Salisbury's central prison for two years, which he described as a "place of study" later in his life, as it gave him and his inmates the opportunity to complete their educations.
In 1964, he was arrested again, this time for possession of a pistol after having been elected deputy organizing secretary of ZANU; at this time, Muzenda had become convinced that the only way to overthrow white colonial dominance was an armed revolution, and began organizing young blacks to receive military training in other African countries, in the USSR and in China. He was soon imprisoned again and remained in jail until being released under the Anglo-Rhodesia agreement in 1971.
Following his release, Simon Muzenda went into exile in Zambia, and later to Mozambique. Failing to draw Joshua Nkomo and his ZAPU movement into a unified political front, he backed Robert Mugabe, who was then also hiding in Mozambique, as the leader of the ZANU Patriotic Front (PF).
After the ensuing guerilla war, which ended with the Lancaster House Agreement, and a brief interregnum of British government while democratic elections were organized, Mugabe was elected as the first prime minister of the new independent Zimbabwe and made Muzenda the deputy prime minister and foreign minister in 1980; Muzenda also retained political power over his home area despite quarrels between his own tribe, the Karanga people, and the Zezuru from which Mugabe stemmed. In 1987, when Mugabe became executive president, Muzenda was appointed as his first vice-president.
In Zimbabwe's early years, Muzenda was generally respected by the people as a no-nosense, plain-spoken man from the working class, but in later years, he appeared more and more crude. In 1990, his campaign for a seat in Zimbabwe's parliament suffered a blow after opposition candidate Patrick Kombayi was shot and left permanently disabled; two state agents were convicted of attempted murder, but pardoned by Mugabe shortly after the trial ended, and even though Muzenda was not publicly accused of being involved in the shooting, it affected his standing with the public.
During the years of Mugabe's rein, Muzenda always gave unreserved backing to the president, even when the regime began muzzling the independent press, curb the activities of foreign correspondents and crushing political opposition. He also participated in Mugabe's land redistribution programme, taking over the Chindito farm, south of Harare, in April 2002 and ejecting the white farm owner, Chris Nel; this incident caused a controversy with the Commercial Farmers Union.
In the two years preceding his death, Muzenda had been in failing health, with problems including hypertension and diabetes; after returning from medical treatment in China in July 2003, he was admitted to the coronary care unit of Harare's main government facility, the Parirenyatwa hospital, where, according to medical sources, he fell into a semi-conscious state. Two weeks before his death, Zimbabwe's state-owned media dismissed reports that he was in declining health, instead announcing that he was making "remarkable progress" towards a full recovery.
Muzenda died on 20 September 2003.