No dia 14 de outubro de 2012, a Seleção alcançou um facto histórico, qualificando-se pela primeira vez ao Campeonato Africano das Nações, competição de maior renome da CAF, e a uma fase final de uma competição internacional ao comando do treinador Lúcio Antunes, num jogo disputado com a equipa dos Camarões, em Yaoundé.
Apesar da derrota na 2º mão em Yaoundé por 2-1 consentida nos últimos minutos, os "Tubarões Azuis" beneficiaram da vitória alcançada em casa no estádio da Várzea por 2-0. É de realçar que o golo apontado em Yaoundé foi do jogador Héldon, através da marcação de um livre direto.
Em março de 2016, Cabo Verde tornou-se a melhor seleção africana na classificação da FIFA, ocupando a 31ª posição. Esta foi a primeira vez que os "Tubarões Azuis" alcançaram o topo do ranking do continente.[3] No entanto, a melhor posição histórica na tabela foi o 27º posto, em fevereiro de 2014.