Båten ble bygget for rederiet Ofotens Dampskipsselskap, Narvik, og ble sjøsatt og døpt 13. mars 1956. Dåpen foregikk altså samtidig med

Narvik. Etter ca. 15 års fartstid ble båten tatt ut av ruten, og erstattet av en katamaran, det vil si en toskrogs hurtigbåt for passasjertransport.

Fra 1. juli til 10. oktober i 1973 gikk båten inn i en melkerute i Indre Ofotfjorden.

Båten ble solgt til Sverige i 1974, og fikk der nytt namn, M/S «Carina».

I 1987 ble båten kjøpt av Border Quest Ltd., Colchester i England, og fikk da tilbake sitt opprinnelige navn.
I 1996 er båten fortsatt registrert under samme navn og eier.

Skroget ble bygget i Sagvåg på Stord, av Ottesen Skibsbyggjeri.
Dette var den første stålbåten Ottesen Skibsbyggjeri bygget. De hadde tidligere bygget 208 trebåter. Ottesen Skibsbyggjeri hadde utført byggingen på en utmerket måte, og fikk ros for arbeidet. Skroget ble slept til Stord Verft, for å gjøres ferdig til levering.
«Tjeldøy» var en smekker rutebåt, som gikk på strekningen Svolvær -

Båten var klasset i Det Norske Veritas + 1A1 I IS, sertifikat for 150 passasjerer.
sjøsettingen, på Ottesen Skibsbyggjeri. Gudmor var Else Høy.

M/S Tjeldøy .
Rutebåt.
29,96 m
5,80 m
2,30 m (Dybde i riss til hoveddekk)
1956
Reinert, Leif og Nils G. Ottesen.
Ottesen Skipsbyggeri. Jensanes. Sagvåg på Stord.
Jern.
Mercedes Benz dieselmotor 395 hk
12 Knop

Ofotens Dampskipsselskap, Narvik