The earliest native people to inhabit Newfoundland and Labrador were the Beothuks. They became extinct quite early under the impact of European settlement. There is much evidence that the first Europeans to reach the island were Vikings like Erik the Red and Leif the Lucky who sailed from Iceland and Greenland to the shores of an island they called Vinland (Wineland) as early as the ninth or tenth century. By the 12th century they had left, but the remains of their settlement have been found and partly restored in L'Anse aux Meadows which is now a United Nations World Heritage site.

Three hundred years later another wave of Europeans ventured across the northwest Atlantic in search of new lands and a passage to the spice islands described by Marco Polo. What they found instead was what seemed like an inexhaustible supply of cod. English, Spanish, Portuguese, French and Basque fishermen came to harvest an increasingly popular and inexpensive food. The fish was dried before shipping back to Europe which made it light and preserved it for the long voyage.

There were so many fish in the waters around Newfoundland that one report claimed that "the sea...is swimming with fish, which can be taken not only with the net but in baskets let down with a stone." For awhile the interests of the navy and the merchants in England discouraged any permanent settlement on the island. The first ship to land each season on a particular shore simply claimed it for the season and exercised the usually despotic rule of the Fishing Admirals.

A novel that captures the early history of Newfoundland is Random Passage by Bernice Morgan, published by Breakwater Books of St. John's.