When I travel, I like to start my day staring down the muzzle of a semiautomatic weapon. Don’t get me wrong, I’ve had my fair share of run-ins with obstinate customs officials, and I certainly enjoy the occasional quarrel with a crooked cabbie, but when it comes to early-morning wake- up calls, there’s nothing quite like the business end of an AK-47 really to get the adrenaline flowing.

Perhaps I should explain. For the past nine days, my travelling companion, Richard, and I have been following Mongolia’s Amur River by canoe, intent on reaching the Russian border before our Mongolian visas expire. Beyond that, we’re hoping to follow it all the way to its mouth on Russia’s Pacific seaboard and, in so doing, to explore the 1,243- mile stretch of river that forms the Russia-China border (much of which can only be reached by boat, hence our chosen mode of transport).

However, travel plans are made to be tweaked, and I’m sure I speak for both of us when I say that, for now at least, we’d happily forgo what remains of our itinerary in return for not being shot.

Our tenth day on the river had dawned as crisp as the frost on our boats. Out on the water, the current was gratifyingly swift and the weather glorious, the azure sky interrupted only by occasional, cotton-bud clouds. The broad river valley rose up to forested hills on either side of us, and eagles and buzzards soared on the thermals created by these hills, keeping tabs on our position as we drifted downstream.

Now, though, we realise they’re not the only ones who’ve been keeping tabs on our position. Anxious not to cross into Russia unwittingly (or, for that matter, illegally), we’ve been on the lookout for the now imminent border post. According to our maps, we’re still well inside Mongolia when we first see the soldiers barrelling down the riverbank. I can’t make out the flag on their uniform, but I assume they’re Mongolian.

As they draw closer, one of them barks a question. I catch the odd word of Russian, but still the rouble doesn’t drop. “Mongolski, da?” I ask in Russian, aware that most Mongolian soldiers speak both languages. “Nyet!” he snaps, with a finality that suggests it isn’t open to discussion. I have visions of giving evidence at the KGB tribunal: “Awfully sorry! There we were, paddling along, when all of a sudden we slipped and fell into Russia.

Bit embarrassing, actually...” How did this happen? How did we miss the border post? How did they ever manage to spot our gleaming red-and-yellow canoes in broad daylight? He motions us to sit down on the riverbank and wait. After an anxious couple of hours, an officer finally arrives, all starched sleeves and aviator sunglasses. “Velcome to Siberia,” he says gravely, in heavily accented English. I half expect him to add, “I’ve been expecting you, Meester Bond.”

It soon becomes apparent that this represents the very pinnacle of his linguistic skills, but it doesn’t seem to matter; minutes later, we’re whisked off to the nearby border post, where the good captain serves us tea and cakes, and presents us with a good-luck card signed by all his personnel. And with that, he stamps our passports, pumps our hands enthusiastically, and welcomes us once more to Siberia.

The name Siberia comes from the Altai word sibir, meaning “sleeping land”. Essentially, the region comprises most of northern Asia and, as such, its statistics defy comprehension: it makes up one-twelfth of the earth’s landmass; it straddles no fewer than seven time zones; and from east to west it measures more than 6,000 miles, or one-third of the northern hemisphere.

But it is perhaps best known for its weather: for seven months of the year, the entire landscape literally freezes solid, with temperatures regularly dropping to -40C (Verkhoyansk, where temperatures as low as -70C have been recorded, is the coldest inhabited place on the planet). In the summer, all but the top few feet of this landscape remain frozen in a rock-hard layer of permafrost that can be hundreds — even thousands — of yards deep. Not for nothing have Russians dubbed Siberia “the land east of the sun”.

Siberia is also known for its salt mines, its exiles and its gulags. For more than 300 years, it was used as a dumping ground for the detritus of Russian society, first by the tsars, and then by the communists. Criminals, dissidents and undesirables were sent to Siberia to die in their millions.

Those who survived (and there were precious few who did) often chose to remain, preferring to scratch out a living from the frozen wastes than return to a life of renewed persecution and certain penury. Today, the whole of Siberia — which comprises an area bigger than America, Alaska and Europe put together — is home to just 33m people, almost all of whom live in the towns and cities along the Trans-Siberian Railway, or in the isolated villages that litter the banks of the Amur.

If our first impression of Siberia is overwhelming, what comes next is something of a shock. A few miles beyond the border we stop at Mangut, a village of rambling log cabins and the odd statue of Lenin. While Rich keeps an eye on our boats, I head into the village to look for somewhere to stay the night. I ask half a dozen people if there’s a hotel in town, but they all look at me like I’ve just stepped out of a canoe.

Times recommends

• Bogus websites are conning hundreds out of their holidays
• The complete last minute holiday guide
• Croatia: the flashing blades of Korkcula