In de periode 1863 – 1873 is de Zeeuwse Lijn aangelegd. In eerste instantie is als eindpunt in Vlissingen een station aan het, gelijktijdig met de spoorlijn aangelegde, Kanaal door Walcheren bedacht. Voor het geplande vervoer van poststukken en pakketten naar de nieuwe Buitenhaven moet een omnibusdienst gaan rijden. Om deze omslachtige werkwijze te voorkomen, is al voor het vertrek van de eerste boot naar Engeland in 1875 naast station Vlissingen-Stad ook het station Vlissingen-Haven in gebruik genomen. Het lage gebouw is zeer langgerekt. In het midden komen twee bescheiden puntgevels. Het middendeel biedt onderdak aan de verschillende stationsfuncties en de douane. In de zijvleugels komen enkele woningen.
Al snel wordt besloten alle treinen naar Vlissingen-Haven te laten rijden en station Vlissingen-Stad te sluiten. Hiervoor krijgt Vlissingen een compleet nieuw stationsgebouw. Het asymmetrische gebouw wordt als kopstation uitgevoerd. Het hoge entreegebouw met stationshal en loketten komt aan de linkerzijde van het L-vormige stationsgebouw. De entree zelf staat schuin op de voorgevel en telt drie dubbele deuren met daarboven een groot venster. Het bouwdeel is bekroond met een opvallende sierlijke klokgevel. Beide hoeken zijn geaccentueerd met een torentje. Links van het entreegebouw staat nog een grote toren met daar achter een lage korte vleugel. Aan de rechterzijde van het entreegebouw komt een lange vleugel van twee verdiepingen. In dit bouwdeel komen onder andere de wachtkamers en stationsrestauratie. Helemaal rechts staat een groot eindgebouw met daarin de douanefaciliteiten. Achter het eindgebouw is een lange lage vleugel te vinden. Naast een aantal dienstruimten, komt hier ook een Koninklijke Wachtkamer. Het station krijgt drie overdekte perrons. Het gehele complex is in 1894 helemaal gereed.
In 1944 raakt het stationsgebouw bij verschillende bombardementen zwaar beschadigd. Na de oorlog verplaatsen laatste veerverbindingen met Engeland naar Hoek van Holland en komt een einde aan de internationale boottreinen. Ter vervanging van het oude gebouw krijgt Vlissingen een relatief eenvoudig nieuw stationsgebouw. Het gebouw is een stuk kleiner dan de voorganger en telt slechts één verdieping. Het complex bestaat uit twee bouwdelen. Terwijl bij het oude gebouw de entree nog aan de stadszijde komt, is die van nieuwe stationsgebouw juist aan de rechterzijde gesitueerd. Belangrijkste reden is de de verwachtte reizigersstroom richting het veer naar Breskens. Aan beide zijden van de voorgevel van het hoofdgebouw komt een tonggewelf. De linker boog accentueert de entree van het gebouw. Hierachter bevindt zich een kleine stationshal met loketten en wachtruimte. De rechter boog accentueert slechts twee ramen van de stationsrestauratie. Links van het hoofdgebouw komt een naar achteren staande vleugel in dezelfde bouwstijl. De linkervleugel biedt achter de opvallend uitgevoerde entree onderdak aan een fietsenstalling. Het nieuwe stationsgebouw staat grotendeels op de fundamenten van het oude gebouw. Een deel van de muren van het gebouw uit 1894 blijft bewaard en maakt deel uit van de achtergevel van het hoofdgebouw en de binnenmuur van de linker vleugel. Ook een deel van de perronkappen en de kap die dwars op het perron staat, blijven bewaard en zijn gerestaureerd. Een deel dient als dak van de linkervleugel. Het nieuwe stationsgebouw is in 1950 in gebruik genomen. Het derde perron is intussen na de oorlog verwijderd. Het ruime voorplein groeit in de daaropvolgende decennia steeds meer uit tot opstelplaats voor het veer naar Breskens.
Door het wegvallen van het goederenvervoer is het emplacement begin jaren ’90 grotendeels opgeruimd. Het middenperron krijgt diezelfde periode een nieuwe overkapping die rust op de kolommen van de oude kap uit 1894. In 1997 is de oude perronkap op het eerste perron aanzienlijk ingekort. Hierbij zijn de kolommen blijven staan en omgebouwd tot lantaarnpalen. Met de opening van de Westerscheldetunnel in 2003 wordt het veer naar Breskens alleen nog geschikt voor het langzaam verkeer. De vele rijbanen op het voorplein maken hierbij plaats voor een wandelgebied. Het stationsgebouw is sinds 2010 een rijksmonument.
Op de foto boven dit artikel de voorgevel en een deel van het ruime stationsplein van station Vlissingen op 24 juni 2023.