Beothukowie wyginęli całkowicie do 1829 r.
Europejczycy odkrywali Nową Fundlandię co najmniej dwukrotnie. Istnieją absolutnie pewne dowody, że ok. 1000 r. wiking Leif Eriksson wylądował na wyspie wraz ze swoją kilkudziesięcioosobowa załogą. Wikingowie założyli tam osadę i spędzili jakiś czas – zapewne kilka pór roku. Potem jednak opuścili ją na zawsze.
Istnieją tylko pośrednie dowody, że już w XIV w., a być może i wcześniej, na wybrzeża wyspy docierali rybacy baskijscy. Członkowie tego ludu zobowiązani byli do zachowania tajemnicy o położeniu swych łowisk, o których bogactwie krążyły legendy. Wydaje się pewnym, że poławiali także na bogatych i współcześnie łowiskach nowofundlandzkich. Można też przypuszczać, że sporadycznie lądowali na wyspie i sąsiednich terenach. Zapewne też przypuszczenia lub nawet jakieś strzępy informacji od nich pochodzące dotarły do Krzysztofa Kolumba i Johna Cabota. Właśnie ten ostatni uznawany jest za oficjalnego odkrywcę.
John Cabot wylądował na wyspie w 1497 w czasie swej wyprawy, która nieskutecznie poszukiwała Przejścia Północno-Zachodniego. Od niego pochodzi też nazwa wyspy.