De Spoorweg-Maatschappij Almelo-Salzbergen neemt in oktober 1865 de spoorlijn tussen beide plaatsen in gebruik. Grensstation Oldenzaal krijgt hierbij een symmetrisch stationsgebouw dat is opgebouwd volgens het vakwerksysteem van houten stijl- en regelwerk, opgevuld met steen. Het middendeel heeft twee verdiepingen en een hoge zolder. Aan de straatzijde heeft een verhoogde ingang met daarboven een balustrade. Op de vier hoeken staan driezijdige uitbouwen met een kegelvormig dak. Het gebouw heeft aan beide zijden lange lage vleugels. Beide vleugels hebben een eindgebouw met puntgevel. Vooral vanbinnen is het stationsgebouw bijzonder rijk versierd, onder andere met veel houtsnijwerk. In Bad Bentheim, aan de andere kant van de grens, komt een soortgelijk stationsgebouw.
In 1887 maakt het vakwerksysteem van de buitenwanden plaats voor stenen muren. Deze muren zijn vervolgens witgepleisterd en van voegen voorzien waardoor het lijkt dat het gebouw is opgetrokken uit natuursteen. Bij de verbouwing is ook de breedte van de zijvleugels aangepast en krijgt het gebouw over de gehele breedte een perronluifel. Een groot deel van de versieringen zoals het houtsnijwerk en verschillende ornamenten verdwijnen bij deze verbouwing.
In juli 1953 brandt het stationsgebouw voor een groot deel af. In eerste instantie wil NS het oude gebouw herbouwen. Later is alsnog voor nieuwbouw gekozen. Het duurt tot mei 1957 tot NS het nieuwe stationsgebouw in gebruik neemt. Tijdens het ontwerpproces wordt duidelijk dat verschillende voorzieningen die bij een grensstation horen niet terug hoeven te keren in het stationsgebouw. Het nieuwe gebouw is dan ook aanzienlijk kleiner en eenvoudiger van opzet dan in de eerste plannen. Het nieuwe lage gebouw is bijna vijftig meter breed en bestaat uit een betonskelet en een strakke betonluifel aan beide zijden van het gebouw. De ingang is geaccentueerd met een zeventien meter hoge klokkentoren. Wanneer in 1976 ook de locomotiefwissel in Oldenzaal niet langer nodig is, verdwijnen de laatste faciliteiten van het grensstation en sluit NS ook de grote stationsrestauratie. Het gebouw staat hierna, buiten het loket, enkele dienstruimtes en een kleine wachtruimte, lange tijd grotendeels leeg.
In 2014 is de complete stationsomgeving van Oldenzaal opgeknapt. Naast een nieuwe infrastructuur rondom het station, met onder andere een tunnel onder het gebouw en het emplacement komt er ook een groot aluminium buizenframe om het stationsgebied te markeren. Verschillende iconen verbeelden de logistiek van het terrein. Ook het gebouw zelf is verbouwd. Zo komt er een serre aan de perronzijde en is het interieur zoveel mogelijk omgevormd tot één grote ruimte. In die ruimte bevinden zich een restaurant en een wachtruimte.
Eind 2023 komt ten oosten van het station een extra kopspoor met perron waar de stoptreindienst uit Zutphen kan keren. De treinen staan zo niet langer in de weg voor de doorgaande treinen vanuit Duitsland.
Op de foto boven dit artikel het stationsgebouw van Oldenzaal met het opvallende buizenframe op 23 november 2014.