Most of the province of Newfoundland and Labrador was covered with ice during the last ice age, but by about 10,500 years BP (Before Present) the ice sheets began to recede. The first human beings to arrive in the province reached southern Labrador almost 9000 BP. Archaeological evidence suggests that these people were descended from Palaeo-Indians (palaeo old), the first human occupants of the hemisphere.

Over time, these first settlers developed a culture that was strongly dependent upon the resources of the sea, and as a result archaeologists refer to these people as members of the Maritime Archaic tradition, which is recognizable by about 7500 BP in Labrador and about 5000 BP on the island of Newfoundland. The Maritime Archaic tradition disappears from the archaeological record by about 3000 BP.

Maritime Archaic bone and stone lances from Port au Choix, Newfoundland ca. 4000-3200 BP. Original artifacts housed in the Newfoundland Museum. Courtesy of Dr. Ralph Pastore, Memorial University of Newfoundland, St. John's, Newfoundland.

About 4000 BP, a people archaeologists call Palaeo-Eskimos reached northern Labrador, and sometime before 3000 BP they reached the island portion of the province. The last of the Palaeo-Eskimos appear to have died out before 1000 BP on the island and a few centuries later in Labrador.

In Labrador, it is possible that the Maritime Archaic people were the ancestors of a people archaeologists call Intermediate Indians although this connection is not at all clear. Sites assigned to the Intermediate Indian culture in Labrador date from perhaps 3500 BP to 2000 BP. Their tools are much different than those of the Maritime Archaic people, and they appear to have been more oriented toward the resources of the interior.

There is a similar debate between archaeologists as to the origin of a people referred to as Recent Indians. On the island of Newfoundland, it is clear that these people are the ancestors of the Beothuk, the aboriginal people of Newfoundland. A number of archaeologists believe that the Recent Indian people of Labrador are the ancestors of the Innu.

The ancestors of the Labrador Inuit are a people archaeologists call the Thule. The earliest Thule sites in northern Labrador are dated to 700 to 800 BP and within a few centuries the Thule had occupied the coast of northern Labrador.