The first people to live along this coast were the Maritime Archaic Indians. Crossing the Strait of Belle Isle some 5000 years ago, they inhabited most of the coast of Newfoundland and Labrador for around 1300 years.

The Maritime Archaic Indians were nomadic, spending their lives in pursuit of migrating animals. Their chief food source were marine mammals, fish and birds, which were caught along the coast during the spring and early summer. The Maritime Archaic Indians spent this time in campsites along the coast's headlands. The headlands also provided opportunities to catch other animals in the woods and wetlands, and fish in the many rivers. Late in the summer, berries supplemented the diet of meat. In the winter, these people moved inland, away from the harsh winds of the coast. Here, they hunted caribou and other small animals. In late winter, the campsites were packed up, and these groups of hunters moved back out to the coast.

For hunting, these people used harpoons and spears to kill large game, and probably used slings for catching birds. It seems that in later years of inhabiting this island, the Maritime Archaic Indians learned how to use bow and arrow from the Paleoeskimos. Their most sophisticated tool was the toggling harpoon. This harpoon had a detachable head that twisted tightly into the wound of captured marine animals. They also made various other hunting tools, like slate bayonets and salmon spears. They made wood, bone and stone carvings using tools made from things like beaver teeth and ivory.

In excavated burial sites, preserved skeletons of these people have been found. It is known that they decorated their dead with red ochre powder. They also placed their dogs in high regard, but it is not known if they were just kept as pets, or if they pulled sleds. The graves indicate that death and burial was a ceremonious affair, but we still do not know what belief system they had.

The story of the Maritime Archaic Indians ends about 4000 years ago. It was during this time that the Paleoeskimos moved into northern Labrador. These people had been moving across the Arctic from the west, eventually moving southward into Labrador and Newfoundland. It is not known if the Maritime Archaic Indians died off due to starvation after several bad years of hunting, if the climate became cold and left them unprepared, or if they were eliminated by the Paleoeskimos.

The Palaeoeskimos were the next people to begin inhabiting this coast, during a period of climactic cooling. Their lifestyle was similar to that of the Maritime Archaic Indians, and they used many similar tools. The Palaeoeskimos are classified into three distinct groups or cultures: Pre-Dorset culture; Groswater culture and Middle Dorset culture. Each groups shared similarites with the others. Generally, as time progresses from pre-Dorset to Middle Dorset culture, tools and hunting practices became more advanced. All groups used the harp seal as a main food source, taking up camp on headlands to catch them whelping. While Pre-Dorset culture depended almost exclusively on these animals, it is thought that the Groswater culture also hunted land animals. It is not known exactly when the last of the Palaeoeskimos – the Middle Dorset culture, left Newfoundland and Labrador, but Inuit legend tells that there were Dorset people in Labrador when the Thule arrived in Labrador 500 years ago.

Recent native cultures to inhabit the island include the Beothuks, Mi'kmaqs, Innu and Inuit. The most recent remains of these people to have been found are at Cow Head and Green Point, which date back some 1000 years ago. It is mostly speculation that these groups used the area where the national park is now, because of their occupation of surrounding areas.

When the Europeans arrived on the east and northern coasts of Newfoundland during the 1500's, they met the Beothuks. It is probably from these people where the term "Red Indians" originated, as they liked to decorate themselves with red ochre powder. Sadly, this native culture is now extinct due mostly to unfamiliar European diseases. Most of the information we have comes from the last known Beothuk, Shanawdithit, through her descriptions and drawings. She died of tuberculosis in 1829.

The Mi'kmaqs lived mostly on the island of Cape Breton, but made regular hunting trips to Newfoundland during the 1600's. According to written reports, it wasn't until the late 1700's when Mi'kmaqs began to move into Newfoundland, as a result of the depletion of game and arrival of settlers into Cape Breton. One of their areas of settlement was in Bonne Bay. Mi'kmaqs developed a reputation for being great woodsmen, and often guided European hunting parties into the interior of the island. Matty Mitchell was one of the most well known. It is thought that he was born in Norris Point in 1850, and still has descendants in the park area today.

The Innu and Inuit probably visited this area as well. It is known that they had trading sessions with the Basque whalers near Port au Choix. These people's main resource were the seals, but they also hunted land animals. The pursuit of these animals through their migration patterns kept them as temporary residents on Newfoundland.