The wooden canoe skims over the smooth waters. As the paddle dips, it creates a tiny whirlpool in the boat’s rippling wake. Around the sandy edge of the shore, the placid faces of moose peer out of the trees. Two lumber out and splash into the river, unconcerned by the presence of humans in a canoe. The icy water is refreshing in the heat, and provides a reprieve from mosquitoes. Behind the trees, the sides of the valley shear up towards a blue sky. The slopes are densely wooded with cedars. This is the Mont des Loups, Wolves’ Mountain, in the heart of Parc de la Jacques-Cartier. here, in the wildernesses of Québec, wolves still run wild in the forests.

The first people in this area of valleys and peaks were Innu, a nomadic indigenous nation, known to the europeans as the Montagnais. In 1535, a French explorer, Jacques Cartier, arrived in St Lawrence Bay. He found diamonds and gold on the cliffs that are now Québec City. Thrilled, he headed back to Paris with his haul, and presented it with a flourish. He was laughed out of court. Despite his name, Cartier was no jeweller: he had found worthless quartz crystals and fool's gold.

In the years that followed, more Frenchmen arrived. While their English contemporaries sought to conquer, the French did not then try to take the native peoples' lands. They wanted to trade.

At the time, hats made of felted beaver fur were much desired by fashionable European gentlemen. So much so, that there were few beavers left in Europe. Canada provided a new hunting ground.

Back in the 16th Century, the point where the St Lawrence River tightens became a base for a rogue collection of hard-bitten survivalists, who spent months venturing deep into the heart of Innu territory to the trading posts at Lac St-Jean. These were the coureurs des bois, or wood runners. They were traders, and were prepared to swap weapons for furs. One rifle, stood on its end, could be exchanged for a stack of beaver pelts the same height. The coureurs des bois faced deadly rapids, canyons, blizzards, bears, wolves, and marauding Iroquois. They must have really wanted those hats.

A route carved out by a river through a valley was the main highway between Québec City and the north for the coureurs des bois. The first part of this route is now preserved as the Parc de la Jacques-Cartier, a national park of outstanding beauty. Thoughtful planning has ensured that the plentiful recreational activities here - including hiking, canoeing and fishing - have made minimal impact on the environment, and much of it still looks exactly as it did when the first europeans arrived. The canoe routes are those used by the coureurs des bois, and by the Innu and huron people with whom they traded. historic trails lead through the dense forest. Following the river up the west side of the valley is one called the Jesuit Trail, named for the French missionaries who soon began to arrive alongside the coureurs des bois.

"To the Jesuits, Amerindian society was really shocking," says Marie Coulombe, one of the park's guides. A Huron brave would present the lady of his choice with a marten pelt. If she consented, he would be allowed to move into her family's longhouse. She was permitted a two-week test drive. "Then, if she didn't like him, she just said, 'Goodbye!' and he had to leave," Marie exclaims. "Maybe she would be pregnant, but this wasn't a stigma among the Hurons. She would try another man instead. If she decided to keep him, he would be considered the baby's father. This was normal, and everybody was relaxed about it." Except for the Jesuits, who marched up this trail from Québec City to burden the locals with conservative European values.

The most popular route along the valley today is an ascent of the Mont des Loups, bounding up wooden steps and over little rivulets through a forest dappled with sunlight. Squeaking chipmunks, straight out of Snow White, gambol across the path. The mountain's wolves stay hidden, preferring to keep away from humans.

Further upriver, Marie leads the way in a thrilling scramble though a maze of overground caverns. Colossal rocks were deposited here by a glacier 10,000 years ago, propped up against each other at unlikely angles. They form a series of grottoes: some bathed in sunlight, some pitch-black, and some still filled with ice in the simmering heat of a Québec summer. In the cracks between the stones, there is here and there an eerie, electric green glow. This is schistostega, known in the park as lightning moss. "We say that there are fairies living in the caverns, and they put the lightning moss here to lure thieves away from their treasure," says Marie. An orange tree frog hops ahead of us as we emerge from the rocks back into the forest.

While the French were trading with the Innu, the English made alliances with an indigenous American league of nations, the Iroquois. Keen to secure control over the fur trade and expand their territory, the Mohawks, an Iroquois tribe, attacked huron lands. The resulting Beaver Wars raged for several years in the middle of the 17th century. equipped with firearms they had bought from Dutch traders, the Mohawks surged westwards into Ontario, driving many hurons as far as Québec City itself. In around 1675, they settled here under the name huron-Wendat, and began to challenge the Innu for control of the beaver fur trade. The clear losers in all this, of course, were the beavers, which were virtually wiped out in the lands near Québec City. The coureurs des bois were obliged to go further and further into the wilderness to seek those valuable pelts.

Plenty of Huron-Wendat people still live in the area, and there is a growing enthusiasm for rediscovering their heritage. In a secluded glade outside the park is Tsonontwan, a collection of teepees, round tents and longhouses built by Régent Garihwa Sioui, an eccentric, hippyish and amiable chief of the Huron-Wendat. This is Régent's home, and he has built the dwellings so that locals and visitors can stay, experiencing something of what life would have been like in a First nations village. Though he has a modern house at the entrance to the site, Régent often sleeps in a teepee when nobody is visiting.

Régent leads me up a narrow track to a ridge, overlooking a stunning view of the Jacques-Cartier River. He speaks with great passion about the land, and about his Huron-Wendat heritage. "We Amerindians invented democracy," he says. Most historians credit the Greeks with that, but Régent is so enthusiastic about his theory that it seems churlish to argue. "The reason America is so powerful is because of the great strength of the native people. We have taught the Euro-Americans everything."

We wander back down to the glade past Régent's house, which is guarded by a pack of huskies. "She is the most beautiful," says Régent, indicating a fearsome-looking hound. "She looks like a wolf." Actually, I think she may be a wolf. She unleashes a throaty growl. It would be a brave visitor who offered one of Régent's dogs a belly rub.

Régent bustles into the kitchen tent, keen to introduce us to First Nations cuisine. Some of Québec's indigenous people, including the Huron-Wendat, did farm vegetables and corn, but in a climate with such severe winters many survived on a hunter-gatherer diet of berries, fish, deer, moose, bear and beaver. "I prefer to eat only meat, cooked rare, and some berries," Régent says. "I can't digest vegetables."

He pours steaming cups of a herbal infusion: "Labrador tea!" After so much talk of an all-meat diet, I can't resist asking if it is made from real labradors. "No, no!" he says. "These are the dried leaves and flowers of a shrub. It is a good drink for hunters. Very calming." The infusion has a pleasant flavour not unlike camomile.

"Now, we will eat," the chief exclaims. He unveils fresh salmon he has smoked, Huron-style, on a wood frame; tender buffalo steak marinated in forest berry juice; and bannique, a rich traditional corn bread. Sated, we retire for a night sleeping as the coureurs des bois slept, on a bed of fragrant spruce branches inside a teepee.

The Parc de la Jacques-Cartier is only the beginning of the vast Laurentides Wildlife Reserve, 3,015 square miles of lakes, hills, forests and rivers stretching all the way from the outskirts of Québec City to Saguenay in the northeast. Like the coureurs de bois, the Innu and Huron-Wendat, what brings people here today is the Canadian wildlife. Most modern visitors plan only to admire it in its natural setting, not turn it into hats.

At a service station north of the Parc de la Jacques-Cartier, biologist Rolland Lemieux is preparing for an expedition. Bespectacled and middle-aged, Rolland looks completely ordinary. He is far from that. For the past 34 years, he has been the best trapper in the area. If you want to catch a lynx, a bear or even a wolf, Rolland is your man. Though he still runs licensed hunting trips in conjunction with the Canadian national parks agency, he traps animals mostly for ecological research and monitoring projects. During his career, he has trapped at least 2,000 bears alive, and returned them unharmed to the wild.

The coureurs des bois soon diversified from the beaver trade into other furs, seeking bears, foxes, wolves and raccoons. Rolland can trap anything - wolves are the biggest challenge, and he took 23 of those alive last winter - but today he is looking for bears. he drives out to a popular spot where bears congregate. he has brought a bait box with him, from which he pulls out, rather unexpectedly, a slab of cake. Bears, it seems, can't resist cake. Any particular type of cake? "Bears will eat anything," Rolland says. "Though, they're not crazy about chocolate."

He arranges the cake on the feeding post, and retreats to a hide. Sure enough, seconds later, a bear pads eagerly out of the trees and gets its paws stuck in. The bear is enormous. It moves fast, but in perfect silence. A few metres away, a porcupine nosing around some shrubs hasn't even noticed.

"It's a male," whispers Rolland. "About four years old."

The area's bears like to use the pineboard sides of the hide as a scratching post when humans are not around. Deep gouges show how fearsome those paws can be - even if the bear in the clearing is currently using his to tear into a Victoria sponge. Having demolished the cake, the bear turns and slips back into the thick foliage.

Rolland is often asked to trap bears that menace campsites and then release them back into the woods at a safe distance. he tells a story about one such bear. He shot it with a tranquilliser dart and loaded into the back of his truck to drive out to the wilderness. Halfway down the highway, it began waking up, and thrashing about. Fortunately, there is a partition between the driver's seat and the back of Rolland's truck - but it is only made of thin Plexiglass. A fully conscious bear would smash it in one swipe. "The other drivers on the road were pointing and screaming," he chuckles.

How did you get it out of the truck?

"I opened the door quickly, and jumped out of the way."

For all his nonchalant style, Rolland never lets his guard down. "Even the two-thousandth time you deal with a bear, you have to treat it like it's the first time," his assistant, Philippe, says. "It's dangerous to relax; Rolland never does. That's why he's still here."

When the coureurs des bois had collected their furs, they canoed and hiked back to what is now Québec City. The city was formally founded in 1608 by Samuel de Champlain, and is now the only walled city in the Americas north of Mexico. It had a vital strategic placement on a rocky bluff over the St Lawrence River, at the furthest point that ocean-going ships could venture from the Atlantic. The British, the French and the Americans often fought over it, and today it retains a European-edged charm.

Vieux-Québec, the old walled city, is exceptionally pretty, historic houses and chapels lining its winding streets. By the late 17th Century, as Québec City began to develop a civic identity, the fur trade began to be regulated. The coureurs des bois were licensed, and renamed the voyageurs. The days of freewheeling fortune-seekers striking out into the wilderness were over. But the legacy of the Beaver Wars between the indigenous nations, and the bitter rivalries between european settlers for control of the north American continent, were coming to an extraordinary climax. In 1756, a war broke out between Britain, Prussia and their allies on one side, and the French, the Russians and theirs on the other, that would expand across the Americas and europe, and even into parts of Africa and Asia. This was the Seven years' War, described by Winston Churchill as the first "world war" for its immense scope. Québec City became the scene of one of the most crucial battles in world history.

Alongside the newer part of the city, stretching from the old fort past the fashionable Avenue Cartier and the elegant Museum of Fine Arts, are the Plains of Abraham. It was here, in 1759, that the famous battle (of the same name) was fought. Sitting now on lawns, amid well-tended flowerbeds and chattering picnickers, it is hard to imagine the British Army swarming onto this plain to attack the French, the smoke of gunfire forming a thick haze among the trees, the slashing of bayonets, and the screaming of the wounded. Today, it is blissfully quiet - though back in town, on the elegant Rue St-Louis, there is a cannonball still wedged in the roots of a tree that is said to date from that battle.

What had begun with a fashion for hats ended with the fall of a mighty empire. The British victory in Québec was the beginning of the end for the French in North America. But Québec City remains, even 250 years later, a monument to that lost world - and a gateway to a wilderness that is still very much untamed.

Getting there
Air Canada has flights from London Heathrow to Québec City, connecting in Ottawa or Montréal (from £450 return).

Getting around
Québec City is best explored on foot as the old city has a one-way system and little parking. But you'll need to rent a car for day trips (from £20 per day).

Three of the best tour operators
Specialising in adventure and ecotourism, ENF Canada offers tailor-made packages all year round. It arranges walking, hiking, cycling, wildlife watching, snowshoeing and crosscountry skiing around Québec and the northern regions of Nunavik, as well as presentations on the area's history, culture or nature. Suggested itineraries include a four-day cycling tour in the Jacques-Cartier area, taking in local fromageries, visits to First Nation sites, and the nearby Montmorency Falls (from £415 per person).

For those travellers who prefer to adventure in luxury, Bridge & Wickers arranges top-quality tours in Québec and all across Canada. These include multi-city routes by rail, self-drive and escorted coach tours. Wilderness tours and wildlife spotting can all be included in the package, as can culinary tours. All tours are bespoke, but suggestions include a ten-day self-drive wildlife watching itinerary, taking in Montréal, Québec City and ample opportunities for bear and whale watching (from £1,614 per person).

Frontier Canada specialises in summer activity tours and winter skiing, catering to most budgets, with accommodation ranging from b&b to luxury chateaux. Gastronomic tours and spa visits can be built in, alongside hiking, fishing and bear watching in the Laurentides Reserve. A seven-day Québec Explorer self-driving tour combines forest and lake scenery with city highlights, including a cruise along the St Lawrence River to view Québec City from the water (from £540 per person).

The article 'The wood runners' was published in partnership with Lonely Planet Magazine.