Rederiet grundades 1991. År 1997 köpte rederiet upp Larvik Line som trafikerade Larvik-Fredrikshamn, och året efter, 1998, köptes även Scandi Line, som trafikerade Sandefjord-Strömstad. Scandi Line bytte namn till Color Scandi Line, men från årsskiftet 2001 blev det Color Line alltsammans. Vid sidan om fartygstrafiken driver man även ett hotell i Skagen.
Åren 1998-99 drevs flygbolaget Color Air som systerbolag till Color Line.