É popularmente designada por "Os Mambas". Não tem alcançado muitos sucessos nas provas internacionais que tem disputado, nunca tendo se classificado para uma Copa do Mundo. Classificou-se cinco vezes para a Copa das Nações Africanas, mas nunca superou a primeira fase.
A primeira partida internacional deu-se em dezembro de 1977, contra a Tanzânia, que saiu vencedora por 2 a 1. Sua maior vitória foi por 6 a 1 contra o Lesoto, em 1980. Neste mesmo ano, sofreu sua maior derrota: 6 a 0 favorável ao Zimbábue.
Na Copa COSAFA, obteve o terceiro lugar em 1997, 2004 e 2009; e um quarto lugar em 2007.
Obteve a medalha de bronze nos Jogos da CPLP de 2010 e a medalha de prata nos Jogos da Lusofonia de 2014.
O jogador mais famoso da seleção foi Chiquinho Conde, que atuou no Sporting. Jojó, que defendeu Boavista e Belenenses, foi considerado o melhor lateral-direito africano na CAN'98, realizada em Burquina Faso. Além deles, Dário Monteiro, que atuou por Académica de Coimbra e Braga, e Armando Sá, que atuou no Benfica, no Villarreal e no Espanyol, são outros jogadores moçambicanos com relativo êxito fora do país. A equipe ainda teve o talentoso Paíto, que chegou também a jogar por Sporting e Braga.
Apesar de ser moçambicano de nascimento, o jogador Eusébio jamais defendeu a Seleção Nacional de Moçambique. O "Pantera Negra" atuou apenas pela Seleção de Portugal. Também nascido em Moçambique, Abel Xavier é outro que nunca atuou pelos Mambas, tendo defendido também o selecionado luso.
Outro moçambicano famoso em Portugal, mas como treinador, é Carlos Queiroz.
Jogadores a atuar fora do paísEditar
Actualmente o melhor jogador a atuar fora do pais é Elias Gaspar Pelembe, conhecido por "Dominguês", e carinhosamente tratado por "Menino Maravilha", que atua na África do Sul. Outros jogadores são Simão Mate Júnior, que atua no Japão, e o defesa central Edson Mexer, atualmente no Rennes.