The first ever mention of a regular ferry service between the two ports was in November 1964, when Sten A. Olsson said that a link served by a newbuild would be established within two years.

The original Stena Germanica, designed by naval architects from Knud E. Hansen, set sail in 1967, offering space for 1,300 passengers and 200 cars/15 trucks. Owing to post-war trade boom between West Germany and Sweden, the route flourished.

The bigger and newly constructed Stena Scandinavica and Stena Olympica entered the service in 1973. In 1982 they moved to the Majnabbe Terminal in Gothenburg, which continues to be the place where the new Stena Germanica and Stena Scandinavica berth.