1845 föreslog greve Adolf Eugène von Rosen att en järnvägskulle byggas mellan Stockholm och Ystad. Järnvägen till Ystad var inte bara av lokalt intresse. Från Ystad gick sedan gammalt regelbundna transporter med post och resande till Tyskland, vilket var huvudskälet till att Ystad planerades bli slutpunkt för von Rosens södra stambana.
Sveriges förbindelser med kontinenten vägde därför tungt i pläderingen för järnvägen till Ystad, och det brukar påpekas att stationshuset fortfarande inte vänder huvudfasaden in mot staden, utan ut mot havet och världen. På grund av ekonomiska svårigheter blev Ystad aldrig stambanans slutstation. Södra stambana drogs istället över Lund, med Malmö som slutstation.
Den första järnvägslinje som utgick från Ystad blev banan till Eslöv via Tomelilla. Den 28 november 1863 påbörjades byggandet av denna linje, den invigdes 1866. Två år senare 1868, dirigerade staten om posttrafiken över Malmö. Detta innebar ett hårt slag mot järnvägsbolaget och Ystad stad, då Ystad hamnade vid sidan av de stora järnvägslinjerna.[pullquote style=”right”]I folkmun gick linjen under benämningen ”Grevbanan”, då styrelsen till övervägande del bestod av slotts- och godsägare mellan Malmö och Ystad.[/pullquote]
Stationsområdet i Ystad ritades av arkitekt Claes Adelsköld och färdigställdes 1865.
Nästa järnvägsförbindelse som planerades var den mellan Ystad och Malmö. Ystadbornas inställning var dock inte särskilt positiv. Stadsfullmäktige såg den nya banan som en konkurrent till Eslövsbanan, vilken staden satsat mycket pengar i. Trots motståndet konstituerades Malmö-Ystads järnvägsaktiebolag 1872. Linjen invigdes 1874.
I folkmun gick linjen under benämningen ”Grevbanan”, då styrelsen till övervägande del bestod av slotts- och godsägare mellan
Malmö och Ystad. Den första tågtidtabellen från 1874 upptog två tåg i vardera riktningen, i maj 1875 insattes ytterliggare ett tågpar. Tåghastigheten var 30 km/h. Med tolv uppehåll tog resan från Ystad till Malmö 3 timmar. Biljettpriset var 60 öre per mil i första klass och 30 öre per mil i tredje klass.
1882 öppnade banan Tomelilla – Simrishamn och sträckan Ystad – Gärsnäs öppnade 1894.