Buiten het dorp Vlissingen, aan de monding van de kreek, stond op het eind van de dertiende eeuw nog een gebouw: het gasthuis. Dat weten we zeker omdat we over een document uit 1271 kunnen beschikken waarin staat dat het gasthuis op 18 oktober van dat jaar een schenking ontving van Aleid, weduwe van de graaf van Henegouwen en zuster van de graaf van Holland en tevens koning van het Duitse Rijk, Willem II. Het “hospitali in Vlissigghen" ontving vijf pond. Het is waarschijnlijk dat dit gasthuis niet in het dorp lag, maar erbuiten, langs de kreek waar die nog bevaarbaar was en het voetveer naar Vlaanderen haar aanlegplaats had.
Het gasthuis was dus al voor 1271 gebouwd en diende, naast het opvangen van zieken, ook voor het bieden van een slaapplaats aan reizigers. Mogelijk was er ook een veerhuis waar reizigers konden eten en drinken en wellicht slapen. Het veer bestond waarschijnlijk al gedurende de hele dertiende eeuw en mogelijk zelfs eerder. Het zuidelijkste deel van Walcheren lag nu eenmaal het dichtst bij Vlaanderen. Omdat er geregelde handelscontacten waren tussen Middelburg, de enige stad die ook buiten Walcheren aanzien had, en de Vlaamse steden, maar ook omdat Walcheren een groot deel van de twaalfde en dertiende eeuw bij Vlaanderen hoorde, was een geregelde veerdienst tussen de eilanden pure noodzaak. Middelburg was een bestuurlijk en kerkelijk centrum in het toenmalige Vlaanderen. De stad had ook een eigen haven die via de Arne, een getijdenkreek, in verbinding stond met het Sloe. Het veer bij het dorp Vlissingen diende daarom vooral personen- en postvervoer.
De eerste ambachtsheer van Vlissingen die we bij naam kennen was Wisse Gilliszoon van Koudekerke. De grond waarop het dorp Vlissingen werd gebouwd behoorde gedurende het grootste gedeelte van de dertiende eeuw tot de bezittingen van zijn familie. De mannelijke stamhouders waren al geruime tijd ambachtsheren van Koudekerke. Zij bezaten daarnaast veel grond op het eiland. In de middeleeuwen vielen bezit en bestuur niet altijd samen. Ieder dorp, toen ambachtsheerlijkheid geheten, werd bestuurd door een ambachtsheer. Soms had deze bezittingen in het dorp, soms ook niet. In het laatste geval behoorden de heren tot de lagere adel. De Van Koudekerkes behoorden tot de hogere adel van Zeeland omdat zij bestuurders waren, maar ook bezit hadden. Na 1300 was de rol van deze familie op Walcheren uitgespeeld. Zij hadden veel geld verloren en moesten hun bezittingen verkopen. Vlissingen werd gekocht door graaf Floris V en die kreeg het idee om een echte stad te gaan bouwen, iets ten zuiden van het dorp, maar met dezelfde naam: Vlissingen.