Apesar de ser uma estreia no Porto do Funchal, o navio de cruzeiros Columbus já navega desde 1988, quando começou como Sitmar FaiyMajesty, para a Sitmar Cruises. Hoje pertence à Cruise & Maritime Voyages.
De evidenciar que o navio já tinha "estreado" na Madeira como Arcadia, quando navegava para a P&O, e depois como Ocean Village, quando pertencia à Ocean Village Cruises.