Les Portugais sont les premiers Européens à explorer l'océan Atlantique. Des marins portugais seraient parvenus à Terre-Neuve avant Jean Cabot, selon certains historiens.
Entre 1898 et 1909, le capitaine Bob Bartlett, de Terre-Neuve-et-Labrador, et l'explorateur américain Robert Peary effectuent trois expéditions vers le pôle Nord.
Durant la dernière glaciation, la majeure partie de Terre-Neuve et du Labrador était couverte de glaces. Celles-ci ont commencé à reculer environ 10 500 ans avant le présent (BP) et les premiers humains à s'installer dans la Province sont arrivés dans le sud du Labrador il y a quelque 9 000 ans.
Les événements entourant l'affaire Lundrigan-Butler, un jugement parmi les plus célèbres dans l'histoire de Terre-Neuve et du Labrador qui concernait deux pêcheurs qui ont été fouettés publiquement pour des dettes impayées à un marchand local.