Em Março de 1964, Armando Guebuza e outros membros do Núcleo dos Estudantes Secundários Africanos de Moçambique (NESAM), decidem abandonar Moçambique para se juntarem à FRELIMO. Para escapar ao controlo da PIDE, a tenebrosa polícia secreta do regime colonial, tiveram que abandonar o comboio em Mapai para fazer o restante percurso até à fronteira de Chicualacuala, a pé, enfrentando o cansaço, a fome e a sede. Uma vez do outro lado da fronteira rodesiana, ainda exaustos, com fome e sede, caminharam mais 30 Kms antes de retomarem ao comboio.
Depois de Salisbúria, hoje Harare, o grupo que integrava Armando Guebuza já na companhia de outros dois moçambicanos, que a eles se juntaram no comboio a caminho de Salisbúria, retomam a viagem para a Zâmbia. No comboio, são presos pela polícia rodesiana, quando se preparavam para abandonar aquele país, e encarcerados em Victoria Falls. Armando Guebuza e os seus colegas são entregues à PIDE e durante aproximadamente cinco meses são torturados para se lhes extrair confissões.
Entretanto, por alturas da sua libertação são presos os guerrilheiros da Quarta Região que se preparavam para abrir a Frente Sul. Apesar de estarem em liberdade vigiada, Armando Guebuza e os seus camaradas decidem vingar-se da acção da PIDE e reafirmar com actos de coragem que a FRELIMO estava activa. Na noite de 24 e 25 de Dezembro de 1964, espalham panfletos, na região Sul de Moçambique, que continham a fotografia do Presidente Eduardo Mondlane. Esta situação forçou a PIDE a divulgar, um comunicado com a lista dos guerrilheiros detidos dando detalhes de cada um deles. Não obstante as intimidações e chantagens da PIDE, retomam o sonho de se juntarem à FRELIMO. Permanecem alguns meses na Suazilândia, como refugiados. Mais tarde, conseguem atravessar a África do Sul e, na Bechuanalândia, um protectorado Britânico, são novamente detidos e ameaçados com a deportação pelas autoridades britânicas. Graças à intervenção do Dr. Eduardo Mondlane, exigindo a sua incondicional libertação, o grupo é entregue ao Alto Comissariado das Nações Unidas para os Refugiados e conduzido para a Zâmbia. Dali, mais tarde, o grupo segue para a Tanzânia, conduzido por Mariano Matsinha, então representante da FRELIMO na Zâmbia.
