O aeroporto tinha uma má fama, por causa da curta pista de pouso e decolagem que, cercada pelo oceano e por montanhas, tornava a aterrissagem complicada até para os pilotos mais experientes. A pista original tinha apenas 1.400 metros de comprimento, mas foi aumentada em 400 metros depois do incidente do Vôo 425 da TAP Air Portugal em 1977, e reconstruída em 2003, praticamente dobrando o tamanho da pista e sendo construída acima do oceano. Em vez de aterrar uma parte do oceano, foram construídas 180 colunas com 70 metros de altura cada, que sustentam a construção.
Por esta obra, o aeroporto ganhou o Outstanding Structures Award, entregue pelo IABSE. Este prêmio é considerado o Oscar das estruturas de engenharia em Portugal.
O projeto do novo aeroporto foi feito pelo português Segadães Tavares.
