We shoved off under the weeping sky of a late June dawn, the frost-scarred concrete tenements of Ust-Kut looming, unlikely spectators for the start of an expedition down Russia’s most pristine major river. Here, at least, the LenaRiver, which flows northward into Siberia, resembled less a primordial waterway than the aqueous graveyard of Russian civilization. It is both, of course. Russia’s expansion beyond the Ural Mountains, a move crucial to its rise as a global power, depended on the Lena to annex a wilderness so inhospitable that few at first would move there readily, or even voluntarily.

In czarist and Soviet Russia, the Lena served as a watery highway into an icebound hell of forced labor and exile, shackles and grief. Vladimir Lenin (né Ulyanov) may have confected his nom de guerre from the river’s name, in honor of revolutionaries like Trotsky who did hard time along its remote shores. Yet the Bolshevik coup that Lenin led in 1917 ushered in the river’s most tragic era, when Joseph Stalin dispatched millions to hard labor and death in Siberia. Countless barges carried inmates from Ust-Kut—once the Soviet Union’s busiest inland port—to prison settlements on the river’s banks.

A trip down the Lena would be a very rare adventure as well as a novel approach to Russia’s ties to its gulag past. Since coming to power in 2000, and especially following his reelection last year, President Vladimir Putin has reinforced executive authority, reasserted Kremlin control over recalcitrant regions, strangled the press and selectively persecuted oligarchs. To this day, Russians are a predominantly rural, small-town people, and to understand how Putin has managed to reverse a democratic momentum dating from Gorbachev’s perestroika of the 1980s, it’s revealing to look not to Moscow and St. Petersburg, where a Western-oriented elite has pushed for liberal reform, but to the hinterland, where Putin enjoys his strongest support.

From the Baikal Mountains more than 2,600 miles east of Moscow, the Lena flows through the taiga (mostly coniferous forest) of the Siberian Plateau into the boggy lowlands and tundra of the Sakha Republic to empty, 2,700 miles later, into the stormy Laptev Sea, within the Arctic Circle. A few hundred miles from the river’s mouth lies one of the world’s coldest inhabited places—Verkhoyansk, where temperatures have plunged to minus 96 degrees Fahrenheit. The tenth-longest river in the world, the Lena is the only major Russian waterway flowing unimpeded by dams or hydroelectric stations. Its waters are clean enough to drink untreated. Along its shores dwell brown bear and wolves, moose and caribou. It is Russia’s river wild, and I had long wanted to sail it.

To travel from Ust-Kut, where my 2,300-mile journey began, is no simple thing. Moscow and the government of the SakhaRepublic (in Russian, Yakutia), a semiautonomous region within greater Siberia, have reimposed restrictions on foreigners’ access to much of the area. I sought help from the polar adventurer Dmitry Shparo, who wrestled permits for my journey from the Sakha authorities, the Federal Security Service (the successor to the KGB), the Border Guards, and the Foreign Ministry. Dmitry also found me a guide, a 37-year-old Muscovite named Vadim Alekseyev. Beefy, with a pig-iron grip and a piercing gaze, Vadim spends six months a year adventuring in the Russian far North, enduring of his own volition the foul meteorological stew of blizzard, ice, rain and wind that Stalin’s victims suffered as punishment.

We would travel in a 17- by 5-foot inflatable raft built to Vadim’s specifications. Half of our 1,430-pound load would consist of fuel for its four-horsepower motor. Vadim carried a double-barreled shotgun, kept loaded. “You never know who or what might step out of the taiga uninvited,” he said.

On the late June day we set out, the weather was balmy, in the low 70s. Cutting a V through panes of liquid pewter speckled with raindrops, we moved with the Lena into fogshrouded woods and hills. Soon we were gliding atop burbling currents dappled with the turquoise of the sky, the green of firs, and the rippling zebra serrations of birches. That evening, as I set up my tent on the riverbank, Vadim lit a fire and cooked a dinner of oats and canned meat, preceded by a clove of garlic as a prophylactic. I was spellbound by the beauty of the taiga—the largest contiguous forest on earth, a primeval preserve here dominated by Siberian fir and Erman’s birch and several species of spruce. Vadim wasn’t moved. “This isn’t the North yet,” he said dismissively.

In the 1550s, Czar Ivan the Terrible of Muscovy crushed Muslim Tatars west of the Urals, spurring Russian expansion into Asia. The Cossack leader Yermak Timofeevich defeated the ruler of Sibir (Siberia) in 1581, whereafter the Russians began to absorb lands farther east. Lured by rumors of forests abounding in priceless furs (mostly sable and ermine) along a great river, a Cossack named Panteley Pyanda first reached the Lena in the 1620s. The Cossacks, from the steppes south of Russia, raised revenues for the sovereign in the form of a levy in furs, which they imposed on the sparse indigenous peoples, the semi-nomadic Evenks and Yakuts.

Opening up Siberia, the Cossacks hastened Russia’s transformation from a middle-sized European country into a Eurasian superpower covering one-sixth of the earth’s land surface. Siberia was eventually to yield resources far more precious than furs, including gold, diamonds, uranium and, most important nowadays, natural gas and oil. In Siberia lie the bulk of Russia’s 72 billion barrels of proven petroleum reserve (the seventh-largest on earth) and 27 percent of the world’s natural gas. Oil alone accounts for 45 percent of Russia’s export revenues, and finances 20 percent of its economy. Only Saudi Arabia pumps more crude.

It was in 1683 that Cossacks founded Kirensk, about 180 miles downstream from Ust-Kut, as an ostrog, or stockaded town. When we arrived, five days out, the morning sun was showering glare over the town’s shacklike shops and low wooden houses, mostly green or blue hovels sinking crookedly into the earth. Vadim deposited me on an antique dock. White poplar seed puffs drifted through the hot air, adding a dreamy languor to the scene disturbed only by groupings of groggy beggars in the doorways, their faces swollen pink from alcohol.

Ivan Pokhabov, a pallid, 27-year-old manager in a cash-register repair firm, and his technician, 22-year-old Pavel Ostrovsky, showed me the town (pop. 15,700). Our first stop was a site that made Kirensk briefly infamous in the last days of Soviet rule: the ruins of a two-story brick building. We entered and climbed carefully down a derelict staircase, into a basement strewn with spent beer and vodka bottles. The building had once been the Kirensk headquarters of the Stalin era’s secret police, predecessor of the KGB. In 1991, the corpses of more than 80 people were uncovered in the basement. They’d been executed around 1938 for alleged “counterrevolutionary” activity—a common accusation in the Terror. “I watched them bring the corpses out of the basement,” Ostrovsky said.

Olga Kuleshova, director of the KirenskRegionalMuseum, said one of her uncles, the head of a local collective farm who was denounced in an anonymous letter to the secret police, numbered among the exhumed. “The executed were our best minds, the light of our nation, the cultured people among us,” Kuleshova said. “There were rumors that others, who were never found, were put on barges and drowned.”

I had heard many such stories during 11 years in Russia, but I was becoming alarmed by the indifference that many displayed toward atrocities in Stalin’s day. To me, the befouled basement execution site showed what little importance people attached to the state-sponsored murders. Could anything like Soviet-era purges repeat themselves now? “Oh, all that could never happen again,” Ivan said. “We have our freedoms now. Everything is permitted.”

A few days later, downriver in the village of Petropavlovsk, Leonid Kholin, a bespectacled collector of historical artifacts for local museums, expressed a different view. “Look, like everyone else, I cried in 1953 when Stalin died. Those who remember Stalin remember the order, the discipline. We hoped Putin might establish the same. But no. As things stand, we have no government, no real courts, nothing. We call our government for help and get no answer.” What about the bloody crimes dominating Stalin’s rule? “It’s better to serve in a battalion with discipline, right?” he said. “Look, we’re half-Asiatic, half-European. We need to maintain our traditions, and for that we need a strong leader. We need discipline.” From Kirensk to the Arctic I would hear Putin faulted, if at all, for not dealing harshly enough with his unruly populace.

In a clearing on a spruce-covered mountainside, Vadim and I spotted a guard tower with a Soviet flag flying above it. Nearby, a 30-foot-high portrait of Lenin—painted in red and white in the stark style of socialist realism—glowered down at us from a two-story concrete barracks. Ayoung man with a shaved head, wearing a blue prison uniform, came running down the bank toward us, waving. He shook our hands and welcomed us to Zolotoy, a correctional labor settlement. Out from the barracks marched a line of ten inmates, tanned and healthy-looking. “Oh, roll call!” he exclaimed, and trotted off to join them.

An officer in khaki emerged from a cabin, peered at us through binoculars and motioned to us to approach. He ran the camp, he said, and the inmates served their sentences logging in the forests. “They don’t look very dangerous,” I said. “Are they petty criminals?”

“Oh, they all robbed someone or beat up people,” he said. “They’re here for a good reason.”

Zolotoy, he said, had once been a logging settlement, but the saw mill had died with perestroika, and the remaining villagers, now mostly pensioners, lived in the derelict huts up on the bank. The inmates helped the villagers with chores. What about the Soviet flag? I asked. “Excuse me, but what’s wrong with the Soviet flag?” the officer said. “It’s always pleasant to see it. It reminds of how things were before all that crap with perestroika began and killed this village.” As we walked back to the boat, he talked disdainfully about political reforms, yet spoke of the beauty of being posted out in these wilds. He shook our hands and saw us off.

The Sakha republic covers 1.86 million square miles—a harsh territory roughly equivalent in size to Western Europe—and accounts for a sixth of Russia’s landmass. Barely a million people live there. Forty percent of it lies within the Arctic Circle, and permafrost hinders agriculture and construction. Summers are brief but surprisingly hot: it can reach 105 degrees. Nowhere on earth do temperatures throughout the year vary so widely: almost 200 degrees.

In the Lena’s delta alone live 36 species of fish, many of them Salmonidae, including the giant and elusive taimen, trout that reach six feet in length and can weigh more than 150 pounds. Vadim would catch, most of all, okun, lenok and succulent nelma, frying what we could eat the first day and smoking the rest in a blackened tin box he brought for that purpose.

As we journeyed into the heat of Sakha’s larch-and-alder lowlands, the fish grew more plentiful—and so did horseflies almost an inch long, with bulbous eyes and a quarter-inchlong proboscis. From our departure around ten in the morning till we pitched camp at eight in the evening, flies circled us relentlessly. Their stab was painful. Worse still were the midges—clouds of tiny gnats. Slapping at them left our arms and faces streaked with blood. These biting insects have played their role in Siberia’s history, deterring escapees from the gulags. “In Old Russia,” Vadim said, “people were put to death by being tied to a tree, naked. The bugs would suck all the blood out of them.”

Sakha’s 700,000 rivers and streams and 708,000 lakes ensure no scarcity of breeding grounds for the pests. We chose our campsites carefully. The rare spot of grassy shore meant mosquitoes (of which I counted three varieties); the commoner pebbly banks, midges. Larch and birch forests sheltered an abundance of man-eaters, whereas pine groves, scented with tangy sap, seemed anathema to all manner of insects. I found the only sure way to escape bites was to stand in the acrid plume of campfire smoke, red-eyed and coughing; Vadim didn’t shave or bathe. “The Yakuts of the taiga don’t bathe,” he said. “Traditional peoples know that skin with clogged pores doesn’t attract bugs.”

Some 700 miles and three weeks out of Ust-Kut, with temperatures falling, we pulled up to Nyuya, a tidy village on a sandy bank. The villagers’ square jaws and long faces suggest something other than Slavic or aboriginal origins. Nyuya’s houses, when built in Siberian style (squat and of dark larch), sported windows of polished glass hung with bright yellow-and-green curtains. No trash littered the dirt lanes. In fact, Germans built most of Nyuya after the Stalin regime exiled them in 1941 from their homeland along the Volga, the GermanAutonomousRepublic, an ethnic entity established during the early Soviet years.

I sipped tea in the kitchen of Sophia and Jakob Deisling, who were in their mid-70s. Their cheerful daughter Anna served tomatoes and cucumbers from their garden. Sophia recalled how, in 1941, Soviet troops loaded her and everyone else in her village in the Volga aboard cattle trains. Thus began a yearlong odyssey that took them through Kazakhstan to Ust-Kut and, by barge, up the Lena. The authorities conscripted her father and all the other young and middle-aged men into the Labor Army. Her mother fell ill, a brother died en route and a sister died of malnutrition. In September 1942, the barge deposited the survivors at Nyuya; they were given axes and ordered to cut the forest. “We were little girls and children and old people,” Sophia said. “How could we saw down trees! But they told us to meet the timber quota or they’d take away our rations—just 400 grams of bread a day!”

Exiled Finns and Lithuanians soon joined them. They might all have perished had not a new director, named Kul, been assigned to oversee their labor; he had the men do the heaviest labor to ease the exiles’ plight, Sophia says. She expressed gratitude for Kul and the Sakha government, which compensates Stalin’s victims with free electricity, firewood and a pension. “May God grant peace to those who called us fascists!” she said, magnanimously, of her torturers.

The GermanAutonomousRepublic was not restored after World War II, and the exiles had to put heated sand in their boots or lose their feet to frostbite, Jakob told me. Still, he seemed to hold no grudges. “Who could we attack?” he said. “The bosses here were just following orders. We all worked together to fulfill the plan!” He paused. “I have preserved my Catholic faith. I pray that God forgive Lenin and Stalin. I know this: I can’t enter heaven with enmity in my heart. We must forgive those who harm us.” As the Russian national anthem came on the radio, his eyes filled with tears.

To part with all notions of freedom, hope, control over one’s destiny—that is nullifying. After returning from such encounters, I tried to share my incredulity with Vadim. He answered with venom. Russians were a “herd” that could “only be ruled by force,” he would say, and Stalin had largely got it right. “I’m more worried about how we’re killing off our wildlife than about how people suffer,” he told me. “As long as the government doesn’t bother me, I really don’t care.”

Once we passed Olekminsk and were nearing our trip’s halfway point, the Lena changed from a swift stream 400 or 500 yards wide into an island-studded watercourse five or six miles across, littered with shoals on which we ran aground. Rainstorms arose suddenly. For five long days I bailed as Vadim, wrapped grimly in his poncho, swung us left and right between angry foaming swells.

The taiga shrank from majestic and dense to sparse and runty, prefiguring the desolating spread of tundra. Yard-high sand dunes appeared on the shore, lending parts of the riverscape a bizarre Saharan aspect. The soothing, bi-tonal ha-hoo! of the cuckoo bird all but vanished; the Siberian chipmunks dwindled in number, and so did the hawks that hunted them. If once a brown bear had come grunting to our camp at dawn to tear up an anthill, and a golden-furred Arctic fox, ears perked, had watched us pack our boat, now our only regular companions were the lonely Sabine gull or croaking raven or cheeping sandpiper. The constant light, at two in the morning as bright as an overcast winter noon, hindered sleep. Yet Vadim and I welcomed the changes. The sun no longer burned, and frequent cold snaps put the mosquitoes out of commission for hours at a stretch. We were sailing through Vadim’s North, and I found it mournfully enchanting.

Almost a month after leaving Ust-Kut, and some 300 miles from the Arctic Circle, we spotted dock cranes, ninestory apartment buildings, ancient log cabins sinking into the permafrost—this was Yakutsk, capital of Sakha, home to 200,000 people. The Turkic Yakuts, who migrated to Sakha from Central Asia in the 12th century, number only about 320,000—tiny numbers indeed, given the area’s vastness, but Russia has always suffered from underpopulation.

My Yakut guide, a 20-something schoolteacher named Tatiana Osipova, was light-complexioned, with narrow eyes and a languid air. She was anything but languid, however. She took me to the NationalArt Museum of the SakhaRepublic, where a Yakut painter, Timofey Stepanov, was exhibiting his work, all of it awash with canary yellows, electric blues and flaming reds. His canvases feature Yakut gods and mythical beasts, princesses and knights on stout horses—figures from the Yakuts’ shamanistic religion, Ayi. His renditions recalled illustrations for children’s books—fantastic and lurid and unbelievable. “Our scenery is so gray, but here you see how much color we have inside us,” Tatiana said.

The atheism taught in Soviet times is still more common than faith, professions of which, in my experience, usually stemmed from other convictions, like nationalism. As it did with her. “We’re one of the most educated minorities in Russia,” she went on. “We take top prizes in national scholastic competitions. Not bad for a people that until just recently lived in balagany,” or crude log dwellings.“We protest on the streets in minus 50 degree weather when Moscow tries to take away our rights. We’re not some people at the end of the earth. We’ve showed the world who we are, and we want our sovereignty. And faith in our religion, Ayi, is good. It’s the basis of our character. Our national struggle continues!” From Tatiana I heard spirited complaints about Kremlin policies for the first time on my trip. It would also be the last.

We sailed out of Yakutsk into merciless wilds. To the west spread the Central Yakutian Plain, an infinity of low, silver-green alders and sandy bog; along the eastern bank, the snow-dappled VerkhoyanskMountains reigned over scraggly taiga; above choppy waters to the north churned gunmetal clouds and whirling skeins of fog. The temperature dropped into the 30s, and a cold head wind raised the surf on a river now nine or ten miles across. Day after day, for ten hours at a stretch, we crashed through breakers that at times forced us ashore. When it seemed nothing could get worse, the clouds emptied their burdens of frigid rain.

Vadim kept his cold blue eyes locked on the horizon. Landing, we would jump out and struggle to haul the boat ashore. Vadim would grab his bottle of red-pepper-flavored vodka and shove it into my benumbed hands. “Drink a drop, quick! To warm up!” I did, and it worked. We then would set up camp. Possibly trying to console me, Vadim said that this summer was freakishly cold. We had feasted on red and black currants before Yakutsk and expected to find them here, along with mushrooms, but there were none—grave omens. “It will be a hungry year,” Vadim pronounced. “Many animals will starve. There will be a lot of shatuny,” or bears that, having failed to eat enough to hibernate, wander the winter woods, at times attacking villagers.

Only a lone soaring black-headed Brent goose or occasional raven broke our sense of solitude. It was late July, and the larch’s tufty leaves were yellowing.

On august 1, we crossed the Arctic Circle. Hours later we spotted Zhigansk—a crescent of gray, wind-battered shacks on a high curving bank. The next evening I found myself shockingly comfortable, sitting with Yuri Shamayev, the Yakut mayor of this village of 3,500 people, mostly Yakuts and Evenks. With high cheeks and intelligent eyes, Shamayev, dressed in loafers, a wool sweater and pressed chinos, looked like he might have been pledging a conservative fraternity in the United States. He lived in what from the outside looked like a condemnable concrete hovel, but inside it was warm and clean, with a refrigerator, a Japanese television and polished wood furniture. His wife made us cucumber and tomato salad seasoned with sour cream, and spread out sausage and salted fish for our delectation. We sipped beer, a luxury.

In the name of their sovereigns, armed Cossack bands had ruthlessly exploited the Sakha region, collecting the fur tax but also demanding “gifts” for themselves—as much as five times the number of furs the state required—or taking women hostage if their men couldn’t or wouldn’t pay. Russian merchants scoured the land for mammoth tusks; in 1821 alone, one merchant exported 20,000 tons. The Soviets forced the semi-nomadic peoples into settlements, which accustomed them to village life and undermined their survival skills. “Our mentality is Soviet,” Shamayev says. “Since we live in extreme conditions—just look at the black rings under people’s eyes here, which are scars from frostbite—we expect the state to help us and give us privileges. But there are too many incentives”—educational institutes, high technology, and the like, available through Moscow, for the SakhaRepublic to want out of Russia. “Our patriotism is left over from Soviet days, and keeps us together.”

I told him I had heard otherwise on previous trips to Sakha. “OK, ten years ago we wanted to separate, but not now. We’re a strategically vital region of Russia. We have too many diamonds, too much timber, coal, and even oil, for them to let us go.” He went on. “Even though we’re descended from Genghis Khan, we’re not a hotblooded mountain people like the Chechens, who love war. Besides, we’re too few to fight like the Chechens.”

In our last three weeks on the Lena, we forced our way through storm after storm, heading north toward Tiksi. Now the taiga gave way entirely to tundra, carpeted in lichen and moss; stony mountains arose on both banks, overflown now and then by golden eagles. As we approached the delta, strong winds prompted us to stop at Tit-Ary, a nearly deserted village of gray shacks and wrecked fishing boats. I spotted crosses atop a sandy hillock, a monument to Finns and Lithuanians interred there—more of Stalin’s victims. A plaque at the base of the tallest cross read: “TORN BYVIOLENCE FROM THEIRNATIVE LAND, FALLEN, BUTNOTFORGOTTEN.” The wind had blown away the sand to expose the coffins. There was something telling in their exposure. Here and there across Russia, monuments have been erected to the crimes of the Soviet era, but they are ill-tended and appear insignificant besides the poverty and neglect of the hinterland.

I hurried back to our boat. We would skirt the delta’s eastern banks, where mountains rose sheer and stony from the water’s edge, to enter the churning Laptev Sea. By then I had grown to admire Vadim. We had quarreled at times. But no matter how high the waves, he never slackened in spirit. He turned desolate riverbanks into comfortable campsites. Nikolai Nikitin, the prominent Russian historian, might have had him in mind when he described Siberia’s Cossack pioneers as “harsh, merciless, but always hardy, steadfast, and courageous, hesitating neither before the boundless Siberian expanses nor its inhospitable weather nor its thousand unknown but unavoidable dangers.” Vadim embodied the frontier spirit that allowed Russia to expand across 11 time zones and turned the country into a superpower (if now only a former one). Vadim told me he admired strength and strongmen most of all—whether good or evil—and had no faith in democracy taking hold in his country. His powerful presence reminded me that, ever since the Cossacks first ventured onto the Lena and made Siberia Russian, the rest of the world had had to take notice.

Seven weeks after departing Ust-Kut, with snowcapped black mountains to the south and a gray sea roiling to the north, we saw, on a ridge, the boxy concrete barracks of Tiksi’s military base. Afrigid rain began to fall. An hour later, we pulled up beneath a blue shack and a beached barge in Tiksi harbor. An army truck stood against the stormy sky, by the shack. We stepped onto the gravel shore and congratulated each other with a handshake. I felt strangely empty. Vadim disdained the comfort that Tiksi’s one hotel would offer and set up his tent onshore. I grabbed my pack and took out my permits, which the military in this closed settlement would surely want to see, and hiked up to the truck that would take me to Tiksi proper.

Like a vision from a gulag survivor’s nightmare, Tiksi’s wind-battered tenements and lopsided larch huts stood bleak and lonely under a bank of fog. Slogans painted in tenfoot red letters (GLORYTO LABOR! CHILDREN ARE OURFUTURE! BLOOM, MYBELOVED YAKUTIA!) covered the weatherworn facades of the hilly center, reminding me that this town of a few thousand souls, mostly Russian military and state functionaries, used to be a bustling Soviet port, as well as one of the USSR’s most secretive places. Tiksi’s population—about 12,000 in Soviet times—enjoyed high pay and privileges for tours of duty that included two months of polar night and 120 days of gale-force winds a year. Now most of the remaining 6,000 or so Tiksians seem stranded.

I and my two hosts, Tamara (a manager at Tiksi’s port) and Olga (a sailor and cook), went to the settlement’s one barrestaurant, an unmarked yellow shack. “What the hell do you want?” shouted the doorwoman, a hefty troll with a bristly mop of peroxided hair. “Why didn’t you let us know in advance you were coming!”

“Is that any way to treat customers?” replied Olga. “Why not just save your breath and slop manure on us instead!” “Yeah!” chimed in Tamara. “We don’t have to patronize your establishment!”

“Then don’t!” The troll slammed the door.

In fact, we had no choice, so we forced our way in, and mounted the stairs to a cavernous bar. The troll flicked on red, green and white Christmas lights strung around the walls. A glum aproned barwoman took our orders. Tamara and Olga spoke of their glorious Soviet past. “We felt like such pioneers out here! The state used to supply us with only the priciest delicacies!” said Tamara. “We knew only luxury! Our husbands used to fly to Moscow just to have a beer!”

The bar filled with a somber crowd in jeans and black leather jackets: delicate Yakut women, pale and high cheekboned, and young men, Russians and Yakuts, mostly sloshed and stumbling. As I tucked into my steak and fries, the troll actually smiled. The Lena’s harsh wilderness receded from my consciousness, and I felt delivered.

A week later, Vadim and I boarded a plane for the flight to Moscow, six time zones back. We flew over mountainous tundra, then a carpet of forest laced with silver rivers. It would take us nine hours to fly across Siberia—terrain the Cossacks had annexed to Russia over the course of a century. For good or ill, their exploit affects us still.