A 3 de julho de 1922, em Angola, era constituída a Companhia Colonial de Navegação, uma empresa de navegação portuguesa que surgiu após o final da I Guerra Mundial e que fazia a ponte entre Portugal e os territórios Ultramarinos.
Constituída em Angola no dia 3 de julho de 1922, a Companhia Colonial de Navegação -CCN iniciou a sua atividade com a aquisição do cargueiro “Ganda” e do paquete “Guiné”, destinados às carreiras de Angola, Cabo Verde e Guiné.
Após a II Guerra Mundial, verificou-se que a frota disponível para a Marinha Mercante era insuficiente e tecnologicamente ultrapassada, pelo que a promulgação do célebre “Despacho 100”, de 10 de agosto de 1945, preconizava a construção de 70 novos navios, incluindo 9 paquetes. A CCN encomendou os paquetes “Pátria”, “Império” e “Uíge” para a carreira de África e os paquetes de luxo “Vera Cruz” e “Santa Maria” para a carreira da América do Sul.
Nos anos 60 verificou-se a intensificação do tráfego marítimo. Com o início da Guerra do Ultramar, os paquetes serão igualmente “mobilizados” para efetuar o transporte logístico de pessoal e material militar para os então territórios portugueses ultramarinos.
Em 1961 entram ao serviço o “Infante Dom Henrique” da Companhia Colonial de Navegação, o “Príncipe Perfeito” da Companhia Nacional de Navegação e o “Funchal” da Empresa Insulana de Navegação. Mais tarde, em 1966, dá-se a entrada ao serviço dos dois últimos grandes navios de passageiros portugueses: o “Amélia de Mello”, da Sociedade Geral, e o “Angra do Heroísmo” da Insulana.
Já nos anos 70, perante o aumento do número de passageiros a darem preferência às viagens de avião, a CCN tentou o aumentou da utilização dos seus paquetes para a atividade turística, embora sem grande sucesso.
Em 1974, fruto da necessidade de reorganização do setor, dá-se a fusão entre a Companhia Colonial de Navegação com a Empresa Insulana de Navegação, dando origem à Companhia Portuguesa de Transportes Marítimos (CTM). No entanto, o ano de 1985 marcaria o epílogo desta companhia, através da sua liquidação e extinção.