Armando Emílio Guebuza nasceu a 20 de janeiro de 1943, em Murrupula, na província de Nampula. Aos 20 anos foi eleito presidente do Núcleo de Estudantes Africanos em Moçambique e na mesma altura ingressou na Frente de Libertação de Moçambique (FRELIMO) para combater o poderio colonial português. Guebuza passou a integrar as chefias da FRELIMO em 1968, no decorrer do segundo congresso do partido, que teve lugar em plena guerra da independência.

Após a independência, foi ministro de várias áreas nos governos liderados pelo primeiro presidente de Moçambique, Samora Machel. Guebuza por duas vezes foi ministro do Interior (1975-1977 e 1983-1985), vice-ministro da Defesa (1980) e ministro-residente na Província de Sofala (1981-1983).
Na sua primeira passagem pelo gabinete do Interior ordenou a saída dos portugueses de Moçambique em 24 horas, apenas com vinte quilos de bagagem.

No primeiro governo de Joaquim Chissano, que sucedeu a Machel, Guebuza foi nomeado ministro dos Transportes. No entanto, a sua ação política mais marcante foi a chefia da delegação governamental que durante dois anos negociou, em Roma, na Itália, as tréguas com a Resistência Nacional de Moçambique (RENAMO). No final de 1994, foi eleito líder do grupo parlamentar da FRELIMO e reeleito para o mesmo cargo após as eleições de 1999.

Em junho de 2002, o Comité Central da FRELIMO elegeu Armando Guebuza secretário-geral e, consequentemente, candidato do movimento às eleições presidenciais de 2004. A 21 de dezembro, a vitória da FRELIMO, por maioria, foi anunciada, permitindo assim que Armando Guebuza se tornasse o terceiro presidente de Moçambique.