Touching down in chill midnight drizzle we stroll directly from the terminal on damp sidewalk to St. John’s’ lone airport hotel. We have a short but restorative sleep, a few coffees, and pick up a rental vehicle that still smells new-car fresh. (Twenty-nine kilometers on the odometer.)

“Watch out for moose,” the rental agent warns.

“Mostly morning and evening?” Deb asks.

“Dawn and dusk, yes,” is the reply. “But they were running around the parking lot at two in the afternoon,” she adds.

Before hitting the road I settle in with another coffee and a stack  of maps and tourist brochures. A piece of art adorns the wall, a schematic of a Grand Banks dory – a museum-quality engineer’s draft as though sketched by Leonardo. Newfoundland lays unfolded on the bed, a glossy paper comforter of gnarly inlets, peninsulas and maritime history. I trace a finger across the map, folds rippling into origami topography. Today, an undulating line will take us northwest from St. John’s through Terra Nova National Park to Twillingate, a peninsular island. A travellers’ guide rests on my lap with Newfoundland’s delicious tagline, “Lost and Found. Lost: agenda. Found: freedom.”

We leisurely buy rations and head out on winding highway – wind- swept expanses of stunted tuckamore forest and marshy lakes. Every so often a blistering vista opens up – hills of solid stone, tree-lined fjords and water dotted with icebergs, bergy bits and bobbing growlers in ivory and dusky blue. Eventually we stop to feast at a small restaurant on a dock – lobster rolls, thick chowder and Iceberg beer, ending the day with a stroll around Twillingate, its harbour jammed with ice – floes and pans buckling into shore. It feels like the inside of a freezer long overdue for defrosting. The air’s watery and frigid. There simply isn’t enough clothing to get warm – as Theroux described Scotland, beauty and harshness in equal extremes.

Morning brings more fog and ice, the island packed like fresh fish. With bellies full of eggs, toast and partridgeberry jam, we layer on clothing and hike a staggered series of frigid headlands. A fog horn howls, lonely and haunting, the sound of desolation, wool and oilskin. We hike to view natural stone arches far out in a bay and circumnavigate Twillingate island in the vehicle – scalloped bays, brightly painted clapboard buildings, beached boats and docks with hanging buoys that from a distance resemble bobbly red earrings.

Like proper tourists we attend a dinner theatre – skits and music – fiddle, accordion, bodhrán, banjo, mandolin, guitar and Newfoundland’s ubiquitous ugly stick. It’s a motley team of talented musicians who feed and entertain us, making something special seemingly from nothing.

From Twillingate we cross The Rock east to west, a long and un- eventful drive (aside from moose watching us pass), to Gros Morne National Park – high stone  tablelands and deep steely fjords. Lunch  at an Irving Oil diner fuels us, a walk through birch and moose drop- pings on the Mattie Mitchell Mi’kmaq Trail invigorates us, and late in the day we arrive at Norris Point, a quaint village tucked in a rugged bay. For dinner it’s moose burgers and Quidi Vidi beer in Rocky Harbour. Total moose encounters: two.

Next day we drive up the west coast for a boat tour of Western Brook Pond – a landlocked fjord, the result of changing sea levels  and shifting glaciers. Cold, icy, even frigid can’t accurately describe the experience. It’s beyond freezing – bone-numbing cold. Paired with scenery. Waterfalls plummet from cliffs of billion-year-old stone, the same stuff we gawked at in West Scotland – original earth from the very first continent, the stuff you can only carbon-date and leave to Stephen Hawking to comprehend.

Excerpted with permission from Gone Viking: A Travel Saga, published by Rocky Mountain Books.