Het verhaal gaat dat de Nederlandse VOC kapitein Willem van der Decken op paasmorgen van plan is om te gaan varen. Het is alleen ontzettend slecht weer en zijn vrouw is erop tegen dat hij gaat varen. Hij besluit toch om met z’n VOC schip op pad te gaan naar Oost-Indië. Hij was van plan om zo snel mogelijk naar Batavia te varen. Het zou hem niet uitmaken of het Pasen was of noodweer. Na een lange tijd bereikten hij Kaap de Goede Hoop. De kapitein geeft orders om het landpunt te passeren, maar z’n personeel vind het geen goed idee. Volgens hem zou het beter zijn om naar de tafelbaai te gaan. De kapitein was woest dat z’n personeel tegen hem inging en hij gooit de stuurman overboord. Volgens de legende zou het hem niet uitmaken of het slecht weer was. Hij ging de Kaap omvaren al moest hij blijven varen tot het laatste oordeel. God of De duivel moest maar bepalen wat zijn lot werd. De duivel nam daarop wraak en nam het schip in z’n macht. Als staf zou zijn schip voor eeuwig moeten blijven rondvaren over de zee. De bemanning aan boord zou niet meer leven en zwijgzaam hun taken uitvoeren. Regelmatig zou de Vliegende Hollander passerende schepen aanhouden met de boodschap om hun brieven aan familieleden af te geven. Deze familieleden zouden alleen al eeuwen geleden overleden zijn.
Er zijn meerdere legendes waarbij het schip van de vliegende Hollander voorkomt. Zo is er het verhaal van de zeeman Barend Fockesz. De Fries presteerde het om in 1678 naar Oost-Indië te varen. Terwijl hier gemiddeld 6 maanden voor stond. De enige manier waarop hij dit kon doen was door een speciaal pact te sluiten met de duivel. In ruil voor z’n snelle tocht moest hij 7 jaar lang in naam van de duivel rondvaren. Hij zou rondvaren op het schip van de vliegende Hollander. Daarnaast is er het verhaal van hierboven met andere personages dan Willem van der Decken. Zo zou de kapitein ook bekend staan onder de volgende namen: Davy Jones, Van Straten, Falkenberg, Van Dam en Van Halen.
Davy Jones zou ook vast zitten op de Vliegende Hollander. Zijn verhaal is alleen anders dan de originele legende. De man werd gezien als een soort duivel of demon die over de zee heersten. Als je op zee zou sterven dan kwam je ziel terecht in de schatkist van Davy Jones. Je ging dan met hem mee op het schip de Vliegende Hollander. De meeste zeelieden waren door deze legende als de dood dat ze nooit meer thuis zouden komen en zouden komen te overlijden op zee. Dankzij deze legende zouden de zeemannen extra hun best doen om het schip veilig terug in de haven te krijgen. In sommige schriften wordt Davy Jones beschreven als een monster, maar hij zou ook in andere gedaantes te zien zijn. Volgens andere verhalen zou Davy Jones eigenlijk Willem van der Decken zijn. Maar door zijn tijd die hij op het spookschip doorbracht zou hij qua uiterlijk veranderd zijn in een monster.
Er zijn verschillende documenten die beweren dat het schip van de Vliegende Hollander uit Terneuzen zou komen. De Engelse schrijver Frederick Marryat beschrijft in 1837 voor het eerst dat het schip uit Terneuzen komt. De schrijver woonde zelf een tijd in de stad. Mogelijk heeft hij hier de volkslegendes gehoord over de Vliegende Hollander en de stad er daarom aan gekoppeld. Vanwege de ligging was Terneuzen ook een belangrijke haven. Vanuit hier konden de VOC schepen vertrekken richting Oost-Indië. Regelmatig trekt Terneuzen het verhaal van de Vliegende Hollander nog steeds naar zich toe. Zo komt het personage voor op evenementen en organiseerde de stad in 2006 een speciaal Vliegende Hollander festival. De VVV heeft zelfs een aantal gebouwen in de stad meegenomen in de legende. Zo kan je zelfs het oude huis van Willem van der Decken bezoeken. Volgens de geruchten zou het in dit huis nog steeds spoken. De stad heeft zelfs speciaal Vliegende Hollander gebak, glazen en bier en er is een wandelroute door de stad.
Ondanks dat het spookschip een legende is en dus niet echt bestaat zou hij wel regelmatig gezien zijn. Er zijn verschillende meldingen van zeemannen die de legende hebben zien varen. In 1880 kwam er zelfs een melding van prins George. Hij ging langs de kust van Australië en zag de Vliegende Hollander in de verte varen. Het schip zag eruit zoals in de legende. Zo zouden de zeilen bloedrood van kleur zijn. De bouw van het schip was volgens een techniek die al lang niet meer gebruikt werd. Naast de prins zelf waren er dertien getuigen die hetzelfde gezien hadden en ervan overtuigd waren de Vliegende Hollander gezien te hebben. In een programma genaamd Mythen der Mensheid is er onderzoek naar gedaan in combinatie met het logboek. Op de dag dat het schip gezien werd op 14 februari 1881 viel een matroos uit de ra. Hij viel eruit omdat hij zo geschrokken was van het zien van het spookschip in de verte. Hij was op slag dood volgens het logboek. Dit voorval staat wel geschreven in het logboek, maar niet dat het spookschip ook echt gezien is. Het vermoeden is dat de fantasie van de prins erop losgegaan is en zo bij terugkomst dit verhaal ophingen.
Het verhaal van de Vliegende Hollander is door de Engelsen verzonnen op basis van de literatuur, maar ook op basis van eigen ervaring. In de zeventiende eeuw waren de Engelsen de grootste concurrent van de Nederlanders in de strijdt om handel. Het gebeurde regelmatig dat de Engelsen afgetroefd werden door de Nederlanders die veel beter waren in het bouwen van schepen. Vanwege de snelheid waarmee ze naar Indië varen leek het wel alsof ze vlogen. De Nederlanders leken geld verdienen ook nog eens belangrijker te vinden dan het geloof. Zo zagen ze de Nederlanders zelfs op christelijke feestdagen uitvaren. Het verzonnen verhaal op basis hiervan is uitgegroeid tot één van de bekendste legendes over Nederland. Vooral omdat iedereen het spookschip weleens gezien denkt te hebben.
