The clues are there for anyone to see – the piles of red rubble on the beaches, the big bones scattered along one section of shoreline – but nobody in the Canadian fishing village of Red Bay had thought to put them together.

“As kids we’d find these little pebbles on the beach, what we thought were pebbles,” Alice Moores, a local woman, told me. “We’d use them like chalk, to draw on the rocks.”

Red Bay, on the coast of Labrador, is a classic 'outport' of Atlantic Canada: clapboard houses perched on treeless headlands, shape-shifting icebergs out on the ocean – and a population of fewer than 300 since a dying fishing industry drove people to seek work elsewhere.

For as long as anyone could remember, children had played with the red pebbles on the stony beaches. But it turned out that no one had remembered back far enough because they weren’t pebbles at all.

“It wasn’t until Mrs Barkham came here in the late Seventies that they were identified as roof tiles,” said Moores.

Not any old roof tiles, either. They were pieces of curved terracotta tiles fired more than 400 years ago in the Basque country of northern Spain and brought to this bay on the rim of the known world in the holds of wooden galleons.

Why this happened is a remarkable story and it was an English-born historian, Selma Barkham, who lifted it from the silt of time.

'New Land' Found After Four Centuries

Forty years ago, her documentary research in the Spanish Basque country revealed a place called Terranova, where Basque mariners had sailed in the 16th Century – just 50 years after Columbus 'discovered' the Americas. Barkham’s work pointed to Red Bay and other sites along the Labrador shoreline of the Strait of Belle Isle as being this 'new land', and archaeological excavations in the Seventies and Eighties confirmed it.

Abandoned workings in Labrador (images: Getty)

In 1979, Red Bay was declared a National Historic Site, administered by Parks Canada, and a museum was opened to tell the story and exhibit the archaeological finds. Its profile was raised internationally in 2013 when UNESCO designated it a World Heritage Site.

Parks Canada can now count itself a major employer in Red Bay – eight people, including Alice Moores, work in its orientation and interpretation centres, and increasing numbers of visitors, mainly from eastern Canada and the northern United States, are boosting the local economy just by making the journey.

About 10 per cent are Europeans, who are coming to discover for themselves this early foothold of the Old World in the New.

Terranova lay at the edge of what was possible. Red Bay still feels like that.

To get there I took an international and a domestic flight to the Great Northern Peninsula of Newfoundland, hired a car, drove 320 kilometres north, caught a ferry across the Strait of Belle Isle to Quebec, turned east into Labrador, drove 80 kilometres up the coast, through settlements so fleeting I didn’t catch their names, only their claims to fame ('Home of Bas Buckle, two times world curling champion'), and watched the road turn to dirt.

For A Fistful Of Reales

I knew I had arrived when I saw the ikurrina, the red, white and green Basque flag, flying alongside the maple leaf by the white wooden church. There was no such greeting for the first Europeans in Terranova, even if this coastline of savage seas reminded them of the Bay of Biscay.

San Sebasatian, where the story begins

Red Bay, which they called 'Butus', was a rare place of calm, a fine natural harbour, and after stepping ashore for the first time in 1542 they established a lucrative industrial operation here for the killing and processing of whales.

The precious commodity they were after was the oil produced by the rendering of whale blubber, which was used in lamps and paint – the castles and cathedrals of 16th Century Europe were decorated and lit from this faraway place.

The men who produced the oil were like modern-day oil-rig workers, putting up with hardship, danger and social isolation for the sake of reales in their pockets. Every spring they set sail from the city of San Sebastian and surrounding ports, taking eight weeks to make the crossing.

Every autumn, before the winter ice froze them in, they sailed back with holds full of whale oil. What happened in between is the story of Red Bay.

It unfolded directly across the water from my accommodation, a cabin balanced above the shoreline of the bay that had been used by the archaeology team in the Eighties. On my first evening I stood at its panoramic windows and watched harbour seals cavorting in the shallows, then turned my binoculars on Saddle Island, which acts as a stopper in the bottle-shaped bay.

Take a peek at Canada's wild west. Vancouver Island: Canada’s Wild West

See the snowy frontier to the north. The Snowy Frontier Of Banff

Deathbed Of Whales And Men

The island is empty now, a rusting shipwreck marooned near its northern shore, its scrubby vegetation dotted with white bakeapple flowers and sea urchin shells dropped by gulls. Once it was a hive of foul-smelling industry, and at its eastern end is a burial site in which 142 Basques from the time of the Spanish King Felipe II are buried in 60 graves.

The following morning, a cold one (“We call this good weather for the capelin,” said the waitress in the Whaling Station restaurant at breakfast), I went over to Saddle Island with Phil Bridle, a Parks Canada guide who helped on the archaeological dig of the island. As we walked the shoreline path, he stooped to point out where he made one of the most poignant finds, a sailor’s finger ring, now on display at the interpretation centre.

What it was all about - the bones of a bow whale

We walked on, past piles of the red debris that, as Alice Moores told me, generations of Red Bay children had used as chalk. Now Phil told me more.

The ships that arrived every spring were weighed down by a ballast of wooden barrel staves and clay roof tiles. The tiles were to roof the 'cooperages' where the barrels were assembled and the 'tryhouses' – kitchens-cum-furnaces – where the whale blubber was boiled up to produce oil.

All along the northern shore of Saddle Island are piles of tile fragments and, nearby, disturbances in the undergrowth marking the sites of these tryhouses and cooperages. The discovery of the roof tiles may have been a Eureka moment, but the find that really lifted the hatch on what happened here lies 10 metres down in the frigid ocean.

Canada's Mary Rose – With A Major Difference

The rusting wreck near the shore of Saddle Island is a red herring in this part of the story – it is that of the Bernier, a collier that broke its moorings in a gale and ran aground in 1965 – but it points the way. Bobbing alongside it are white buoys marking the resting place of a ship that suffered the same fate precisely 400 years earlier.

The San Juan was a 22-metre Basque whaling ship and, when she sank in 1565, the silt and cold of the seabed acted as a mummy shroud, preserving a body of history. This is Canada’s Mary Rose – with one crucial difference.

Acting on a tip-off from Selma Barkham, who had found reference to a ship that sank at Butus, underwater archaeologists discovered her remains in 1978. But after bringing her timbers to the surface, retrieving precious and revealing artefacts from her carcass, and measuring, photographing and recording her, they returned the San Juan to the preservative environment of the seabed.

“The Mary Rose took a different route which was logistically impossible here,” said Cindy Gibbons, Parks Canada’s site supervisor, adding, with perhaps a touch of one-upmanship: “UNESCO recognises what we did here as best practice for preserving wooden shipwrecks.”

A wandering iceberg drifts by in the Strait of Belle Isle

Now that the San Juan is back where she belongs, the nearest you will get to the ship is the 1:20 scale model in the interpretation centre. Around it are displayed objects found in and near her hull – binnacle, sandglass, astrolabe, compass (still with bits of glass), capstan, anchor, bilge pump, barrel staves, harpoons, cooking pots – while in the orientation centre nearby is an original chalupa, one of the small, fast rowing boats used to actually hunt the whales.

So what of the whales, the unwilling co-protagonists of this unique passage of history? The Basques targeted right whales and bowheads, which were slow and plentiful.

The Cold Wind Is All That Remains

The skeleton of one, an 18-metre-long bowhead, is on display in Red Bay 'town centre' (the village hall, named in honour of Selma Barkham). It has no tail bones or flippers because these were removed for processing – the carcasses, weighing up to 90 tonnes, were rotated in deep water like a doner kebab while being stripped of blubber.

Some of this work also seems to have been carried out on land since one section of shoreline, known as Boney Shore, is littered with whale vertebrae, ribs and skulls. It was still good weather for the capelin when I visited this cetacean graveyard.

A cold wind whipped across a harbour where commercial fishing came to an end 20 years ago as surely as whaling before it. The steely waters are empty now save for buoys and gulls – and a sunken galleon from faraway that never went home.

Red Bay National Historic Site is open from early June to the end of September: 9am-5pm early June and late Sept, otherwise 9am-5.30pm, daily. Adults A$8, children (six-16) A$4. A boat to Saddle Island leaves hourly: A$2 per person.

Visit your local Flight Centre store or call 131 600 for more advice and the latest deals on travelling to Canada.

This article was written by Nigel Richardson from The Daily Telegraph and was legally licensed through the NewsCred publisher network.