Tussen 1850 en 1880 ontstonden verschillende initiatieven voor het opzetten van een spoorverbinding tussen Denemarken en Duitsland. Nadat pogingen voor een verbinding via Rødby strandden, richtte men zich tot Falster. Op 23 mei 1873 werd aan de Deense magnaat Carl Frederik Tietgen toestemming verleend voor de aanleg van een spoorlijn tussen Nykøbing Falster en een plaats aan de zuidkust van Falster, waar een haven zou worden gebouwd voor een veerverbinding met Duitsland. In de concessie werd opgenomen dat de spoorlijn, de zuidelijkste uitloper van de Sydbanen, op 1 juni 1886 klaar diende te zijn. Met een vertraging van enkele weken werd de spoorlijn tussen Nykøbing en Gedser op 27 juni 1886 geopend.
De eerste jaren werd de treindienst in eigen beheer uitgevoerd. Op 1 januari 1893 werd de spoorlijn overgedragen aan de Danske Statsbaner, die ook de exploitatie overnam. Op 30 september 1903 werd de veerbootverbinding met Warnemünde ingesteld. In datzelfde jaar kreeg Gedser een nieuw stationsgebouw. Omdat men een militaire aanval vanuit Duitsland vreesde, kreeg het station twee verdedigingstorens met naar het zuiden gerichte schietgaten.
Een trein naar Kopenhagen vertrekt uit het station van Gedser, 20 augustus 2002. Aan weerszijden de verdedigingstorens.
Na de gereedkoming van de Fehmarnsundbrücke in 1963 werd een groot deel van het internationale treinverkeer verplaatst naar de route via Rødby en werd de verbinding tussen Gedser en Großenbrode gestaakt. Nadat ook de spoorpont tussen Gedser en Warnemünde in 1995 was opgeheven, verloor de lijn Nykobing F - Gedser zijn internationale betekenis. Gedser, een plaats van nog geen 1000 inwoners, levert te weinig vervoer op en de tussenstations nog minder. Zij zijn in de loop der tijd dan ook alle gesloten. Alleen de wisselplaats in Fiskebæk bleef in gebruik om treinen te kunnen laten kruisen. De treindienst tussen Nykøbing en Gedser werd gereduceerd tot zes treinenparen per week. DSB wilde de verliesgevende lijn al geruime tijd sluiten. Dit vond plaats per 12 december 2009. De infrastructuur blijft behouden, zodat de mogelijkheid blijft bestaan deze spoorlijn te reactiveren.
In de oude locomotiefloods bij het station van Gedser bevindt zich een particulier spoorwegmuseum GedserRemise. In de zomer van 2015 reden er toeristische treinen.