Das Trajekt Warnemünde–Gedser war die älteste deutsche Fährverbindung nach Skandinavien und die erste internationale Eisenbahnfährverbindung. In Deutschland hatte das Trajekt Verbindung an die Lloydbahn über Rostock nach Berlin, in Dänemark schuf die Bahnstrecke Nykøbing–Gedser Anschluss an die dänische Hauptstadt Kopenhagen.
Die Dampferverbindung zwischen Stettin und Kopenhagen, seit den 1840er Jahren, wurde 1873 von einer kürzeren Postdampferverbindung zwischen Rostock und Nykøbing (Falster) abgelöst. Sie wurde ab 26. Juni 1886 nach Warnemünde zu dem neuangelegten Hafen von Gedser verlegt, auf ihr verkehrten zunächst die Raddampfer Kaiser Wilhelm und König Christian.
Im Jahr 1900 begannen umfangreiche Bauarbeiten in Warnemünde. Die Stadt Rostock übernahm dabei die Aufschüttung des neuen Bahnhofsgeländes, den Umbau der Molen, den Bau des neuen, 1,1 Kilometer langen Seekanals sowie den Bau einer Brücke über den Alten Strom, um den neuen Bahnhof mit dem Ort zu verbinden. Das Empfangsgebäude des alten Bahnhofes stand der Streckenverlängerung im Weg. Deswegen wurden die Gleise direkt durch den Mittelteil des Gebäudes mit der ehemaligen Empfangshalle geführt, wodurch eine Art Tunnel entstand. Das neue Bahnhofgebäude entstand zwischen dem neuen Seekanal und dem Alten Strom.
Am 30. September 1903 wurde in Anwesenheit von König Christian IX. von Dänemark und Großherzog Friedrich Franz IV. von Mecklenburg-Schwerin die Eisenbahnfährverbindung eröffnet.
Während des Ersten Weltkrieges blieb die Linie ohne Einschränkungen in Betrieb, da Dänemark in diesem Krieg neutraler Staat blieb. 1920 gingen die mecklenburgischen Schiffe auf die Deutschen Reichseisenbahnen über. Die DSB brachte 1922 das Fährschiff Danmark in Fahrt, das die Prinsesse Alexandrine ersetzte. Mit der 1926 in Dienst gestellten Schwerin wurde von der Reichsbahn ein modernes Fährschiff in Fahrt gebracht, das in der Werbung auch als „Weißer Schwan der Ostsee“ bezeichnet wurde. Großzügige Aufenthaltsräume, Restaurants und ein Promenadendeck machten die Fahrt für die Passagiere besonders angenehm. Auf diesem Schiff war erstmals der Pkw-Transport per Achse (vorher nur Bahnverladung) möglich. Das Fährschiff Mecklenburg wurde modernisiert, die Friedrich Franz IV. außer Dienst gestellt.
Mit Beginn des Zweiten Weltkriegs wurde die Schwerin vorübergehend an die Kriegsmarine abgegeben, kehrte aber bald auf die Linie zurück. Während der Besetzung Dänemarks durch die Wehrmacht am 9. April 1940 wurden von der Mecklenburg und der Schwerin Teile der ersten Invasionstruppen nach Gedser übergesetzt, wobei die Mecklenburg als planmäßige Fähre mit getarnten Soldaten eintraf. Das Fährschiff Schwerin wurde im Februar 1944, als es sich zu einer Kesselreparatur in der Rostocker Neptun-Werft befand, durch Bombentreffer schwer beschädigt und nicht wieder repariert. Die dänische Fähre Danmark wurde 1943 und im März 1945 vom dänischen Widerstand im Hafen von Gedser erst schwer beschädigt und dann versenkt. Mit der Besetzung Rostocks und Warnemündes durch sowjetische Truppen wurde der Fährverkehr völlig eingestellt. Die noch einsatzbereite Dampffähre Mecklenburg wurde als Reparation der Sowjetunion zugesprochen und von ihr 1947 an Polen übergeben.
Nachdem der Fährverkehr 1947 durch die DSB mit der gehobenen und modernisierten Danmark wieder aufgenommen worden war, bemühte sich die ostdeutsche Deutsche Reichsbahn, ein eigenes Fährschiff für die Linie zu bekommen. Pläne für den Ankauf eines Schiffes im Ausland scheiterten. Übergangsweise wurden Personen mit gecharterten Seebäderschiffen der Weißen Flotte befördert. Erst mit der Indienststellung des Neubaus Warnemünde im Jahr 1963 konnte die Deutsche Reichsbahn die Strecke wieder paritätisch mit der DSB bedienen, die ab 1968 das Fährschiff Kong Frederik IX einsetzte. Die Reichsbahn war bemüht, hochwertiges Wagenmaterial für die Verbindung bereitzustellen, so fuhr von 1963 bis Ende der 1970er Jahre der Schnelltriebwagen VT 18.16 ab 1964 auf dieser Strecke für den Zug Neptun.
Bis zur politischen Wende in der DDR wurde die Bahnverbindung Kopenhagen – Warnemünde – Berlin für den Verkehr zwischen Skandinavien und der DDR sowie von und nach West-Berlin als wichtig angesehen, in den letzten Jahren jedoch eher aus politischen Gründen. Es gab täglich zwei Schnellzugpaare (Tageszug Neptun, Nachtzug Ostsee-Express) nach Berlin Stadtbahn. Nach dem Mauerbau in Berlin (ab 1962) begannen die Züge im Bahnhof Zoo und hielten im Bahnhof Friedrichstraße und im Ostbahnhof (1987 bis 1998 Berlin Hauptbahnhof). Dort wurden bei lokbespannten Zügen Wagen des Binnenverkehrs zugestellt, die bis Rostock Hauptbahnhof mitliefen und auch von DDR-Reisenden benutzt werden durften. Die internationalen Wagen waren, zumindest zeitweise, abgeschlossen und ohne Übergang zum übrigen Zug. Dies und die peniblen Kontrollen der DDR-Grenzer und des DDR-Zolls führten dazu, dass die Züge bei den Skandinaviern wenig beliebt waren. Ende der 1980er Jahre bestanden der Neptun und der Ostsee-Express nur aus ein bis drei Schnellzugwagen, die von DR und DSB im Wechsel gestellt wurden. Mit dem Vindobona konnte man im Transit von Berlin nach Wien weiterreisen.
Die Öffnung der Grenzen der DDR brachte der Eisenbahnfährverbindung noch einmal einen Aufschwung. Der Ansturm der Reisenden führte dazu, dass bis zu acht Eisenbahnwagen pro Fährfahrt transportiert werden mussten. Gleichzeitig stieg die Zahl der überzusetzenden Pkw stark an. Für diesen Ansturm waren die Schiffe der Linie nicht ausgelegt. War das Auf- und Abziehen der Schnellzugwagen noch problemlos möglich, so war die stark gestiegene Zahl der Pkw und Lkw nur mit Schwierigkeiten zu bewältigen. Weder das Fährschiff Warnemünde noch die Kong Frederik IX verfügten über besondere Autodecks. Um die Kapazität voll ausnutzen zu können, mussten Pkw, Lkw und Sattelzüge oft umständlich und zeitaufwändig in das Wagendeck rangiert werden. Die Zufahrt zu den Abfertigungseinrichtungen von der Autobahn A 19 nach Warnemünde war nur durch die oft durch Staus beeinträchtigte Rostocker Innenstadt möglich. Später ging die Zahl der Bahnreisenden immer stärker zurück, da die Zugverbindung langsam war und altes Material eingesetzt wurde – auf der dänischen Seite fuhr der Berlin-Express als Nahverkehrszug von und nach Kopenhagen. Das Auto war auch hier zum bevorzugten Verkehrsmittel geworden; eine autogerechte Fährverbindung wurde 1993 durch Umbau der Fährbrücke in Gedser zum Anlegen mit dem Heck, bei der Warnemünde durch Reaktivieren der verschweißten Heckklappe kurz vor ihrer Ausmusterung geschaffen.
Die Transportkapazität der Fährverbindung Warnemünde-Gedser betrug 1996 0,037 Millionen Lkw, 0,18 Millionen Pkw sowie 1,4 Millionen Passagiere. Der Eisenbahnfährbetrieb auf der Verbindung Gedser-Warnemünde wurde im September 1995 eingestellt. Seitdem wickelt die deutsch-dänische Reederei Scandlines den Autofährbetrieb nach Gedser über den Rostocker Überseehafen auf der östlichen Seite der Warnow mit den zwei Fährschiffen Kronprins Frederik und Prins Joachim ab.
