Só em 1975, após conquistar o Campeonato da Madeira novamente é que o Nacional pode finalmente participar no Campeonato Nacional da III Divisão.
Em 1977/78 ascendeu à II Divisão e em 1987/88 estreou-se no primeiro escalão. Nesse primeiro período na I Divisão que durou até 1991 destaca-se uma histórica vitória no Estádio das Antas por 1x2 que espantou o país desportivo.
Caído na então II Divisão de Honra o Nacional manteve-se a meio da tabela durante 3 anos, caindo para a II Divisão B no ano seguinte.
Entrando num período de crise os alvinegros, voltaram a subir ao segundo escalão para cair novamente ao terceiro escalão, com mais um último lugar. Com o Rui Alves na presidência o clube começa a modernizar-se iniciando a construção de um novo estádio na Choupana com o objectivo de abandonar o Estádio dos Barreiros. Em 1998 inicia-se a construção do Estádio Engenheiro Rui Alves que é inaugurado em 2000. No primeiro dia de Junho de 2007 e depois de feita uma ampliação que daria ao estádio uma maior capacidade, seria rebaptizado de Estádio da Madeira.
Só em 1999/00 o Nacional voltaria a subir à II Liga, mas pouco depois, em 2001/02 estava de regresso ao escalão maior do futebol português.
Após um 11º lugar no ano do regresso, o Nacional orientado por Casimiro Mior consegue a melhor classificação da sua história, acabando em 4º lugar e apurando-se para a Taça UEFA onde se estreou na época seguinte defrontando os andaluzes do Sevilla.
Em 2004/05 o Nacional conseguiu o resultado mais espectacular da sua história vencendo em pleno Estádio do Dragão o FC Porto com um esmagador 0x4.
O clube volta a participar na Taça UEFA sendo eliminado na 1ª eliminatória pelo Rapid de Bucareste na época 2006/07, depois de no campeonato anterior ter conseguido um excelente quinto lugar.
2009 foi o ano em que o Nacional igualou a melhor classificação da sua história conseguindo também chegar às meias-finais da Taça de Portugal, onde acabou por ser eliminado pelo Paços de Ferreira.
Um ano depois o Nacional fez uma excelente carreira na Liga Europa, eliminando os russos do Zenit com um 4x3 no Funchal e um 1x1em São Petersburgo, qualificando-se para a fase de grupos da competição onde não conseguiu seguir em frente pela forte oposição de Werder Bremen e Athletic Bilbau.
A época de 2010/11 valeu nova qualificação para a Liga Europa, além de uma nova presença nas meias-finais de uma Taça, desta vez a Taça da Liga, para novamente perderem a passagem para a final por culpa do Paços de Ferreira.
No século XXI o Nacional tem sido um exemplo de boa gestão. Conseguindo construir um estádio novo, reestruturar-se com a nova academia e lançando jovens promessas como Rúben Micael.
Com dois quartos lugares e quatro presenças nas competições europeias, o Nacional conseguiu neste início de século não só ombrear com o grande rival Marítimo como em algumas situações ultrapassá-lo. Na época de 2016/17 voltaria a descer para o segundo escalão, subindo na época seguinte para o principal patamar do futebol português como 1°classificado da Segunda Liga.
Desde o início do século XX, uma importante parte dos Madeirenses sentiram a necessidade da região possuir um estádio polivalente pois, modalidades como o futebol, atletismo e outras, passaram a ter um papel importe na sociedade madeirense do início do século.
O Nacional, em 1920 oficializa a intenção de construir um estádio, que não só servisse para a prática do futebol mas também para outras modalidades.