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 2024, a seleção supera a campanha de 2013 e faz a sua melhor campanha no Campeonato Africano das Nações. Ao comando do treinador Bubista, a seleção qualificou-se para o torneio, foi sorteada no pote 3 e ficou no Grupo B, junto com Gana, Egito e Moçambique. Estreou no dia 14 de janeiro, onde, surpreendentemente, venceu Gana por 2-1. Na rodada seguinte, aplicou uma goleada de 3-0 em Moçambique, garantindo a classificação direta no grupo, e por fim, empatando com Egito por 2-2, terminando como líder do grupo, obtendo 7 pontos. Nos Oitavos de Final, enfrentou a Mauritânia que também foi uma surpresa por ter eliminado a Argélia na fase de grupos. Durante a partida, aos 87 minutos, o goleiro mauritano Babacar Niasse comete uma penalidade, e Ryan Mendes converte, decretando a classificação por 1-0 dos "Tubarões Azuis". Nos Quartos de Final, enfrentaram a África do Sul em uma partida que durou 120 minutos sem golos. No momento das penalidades, o guarda-redes sul-africano Ronwen Williams também fez história e defendeu 4 de 5 cobranças cabo-verdianas, culminando na eliminação da seleção através das grandes penalidades. Apenas Bryan Teixeira conseguiu converter a única cobrança para Cabo Verde. A disputa por pênaltis terminou em 2-1, terminando assim a campanha histórica.[3]
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.[4] No entanto, a melhor posição histórica na tabela foi o 27º posto, em fevereiro de 2014.