A Companhia Nacional de Navegação (CNN) constitui-se em 4 de abril de 1918, resultante da transformação da parceria marítima Empresa Nacional de Navegação a Vapor para a África Portuguesa (ENN), em Sociedade Anónima. A transferência do património da ENN para a CNN fez-se a 1 de julho de 1918, mantendo-se a frota e as cores da anterior Companhia.
Em 1922 a CNN faz a sua primeira aquisição – o paquete holandês Sindoro a que se dá o nome Pedro Gomes e no ano seguinte o Albertville rebatizado Angola (III). Estes navios asseguravam as carreiras regulares entre o Norte da Europa e a África Ocidental.
Em 1933 a CNN sofre uma gravíssima crise sendo gerida, até outubro de 1936, por uma comissão administrativa nomeada pelo governo. De 1938 a 1945, adquire os paquetes S. Tomé, Angola (IV) e Moçambique destinados à carreira de África. Em 1952 inaugura a carreira do Oriente com os paquetes India e Timor. Ainda em 1952, num período de ressurgimento da Marinha Mercante Portuguesa, a CNN encomenda a construção do Niassa (II) destinado à carreira da África Oriental. Em 1961 é adquirido o Príncipe Perfeito, o maior navio da Companhia e o segundo maior de todos os paquetes portugueses. Durante a década de sessenta os navios da CNN farão regularmente a linha de África.
Em 1972, através de fusão das companhias, a CNN adquire os navios da SG e em abril de 1974, a CNN possuía ainda cinco navios empenhados no transporte de passageiros e bagagens das ex-colónias para Portugal. Em 1985 o governo decreta a liquidação da Companhia Nacional de Navegação.
Ao longo dos mais de cinquenta anos de existência esta Companhia possuiu cinquenta e quatro navios com deslocamento variando entre as 221 toneladas De arqueação bruta – Pirata Azul (1972) e as 19.393 toneladas do Príncipe Perfeito (1961), que inclusive era o navio com maior lotação conseguindo transportar 1000 passageiros, contrariamente ao Save (1951), que era o navio com menor lotação, podendo transportar doze pessoas.