Easy riders.

LOOK, I'm not Hemingway, Marco Polo, or Lewis or bloody Clark. I don't kayak, hike, or bike, but I do know I'm not the only traveler in Mongolia to have gone through a moment of despair, regret (what was so wrong with Cancun anyway?), and panic. And why not? We were somewhere remote in the country that defines remote and our guide's "short cut" had more than a touch of the Donner Party about it.

Were those really vultures, dark, enormous, and optimistic, circling over our dusty and exhausted bus as it bounced, creaked, juddered, and shuddered along the unpaved road that wound across an empty plain that made the Mojave look like the Garden of Eden? Yes, they were vultures. Big ones. Mean ones. Hungry ones.

Hours, hours, bouncing and juddering hours later, broken only by a grim little picnic by a grim little lake previously denuded of fish by dynamite-toting Chinese, we arrived at Lun, a Mad Max scrap of a settlement that shared only a syllable with the British capital, in the hope of refueling the bus. Lun's wreck of a gas station had gas. It had pumps. It had an attendant. What it didn't have was electricity. No electricity. No pump. No gas. The power was out all over eastern Mongolia, but the attendant thought that a lady who lived nearby might have a stash of gas, and that stash of gas could be for sale. She did, and it was.

The impossible has a way of happening in the land of the Mongols. They are a people too far-flung, too poor, and too strange to survive. And yet they have. They survived the collapse of the khans' huge empire, they survived the centuries of Chinese oppression that followed, they survived even the brief, brutal, and bizarre rule of a crazed Baltic baron, and, finally, they survived the decades of Communist dictatorship that ended only in 1990.

Now at last this nation of nomads, lamas, herdsmen, shamans, miners, bureaucrats, and trainee city slickers is back in charge of its own destiny. And as in so many other parts of the old Soviet bloc the first sign of a better future is the return of the long-suppressed past. In Mongolia that can only mean one thing: You Know Who is back. Genghis! In the Communist era, Genghis Khan (or, more accurately, Chinggis Khaan) was regarded as a distinctly disreputable figure, a man best not mentioned by the politically prudent. Not anymore.

Brushed, scrubbed, rehabilitated, and thoroughly whitewashed, the old monster has been transformed into a lawgiver, philosopher, and all-round decent guy. "Yes," I was told, "he was a mass murderer, but that's how war is." Besides, he was "provoked" (it's a long--and utterly unconvincing--story). Butcher no more, Genghis now shines as a symbol of Mongolia's lost glory and newfound confidence. There's even talk of moving the capital from Ulan Bator (Ulaanbaatar) to the spot that Genghis picked, Karakorum (Kharkhorin), these days a tumbledown town distinguished only by a magnificent monastery having, awkwardly, no connection to Genghis. In fact, almost nothing in Karakorum has. Well, there is a modern monument--part Trump, part Brezhnev, all disaster--dedicated to the Mongol empire, but, like Mongolian cuisine, it is best passed over in silence.

Fortunately, there's more in Mongolia for Genghis fans than Karakorum, including Chinggis cigarettes, Chinggis beer, and the alarming Chinggis vodka. In Ulan Bator, Chinggis has given his name to the best hotel, a wide avenue, and a good place to munch some mutton. Over in the national history museum, previously preoccupied with the exploits (stupendous) of the Mongolian Communist party, the Commies are out and Genghis is in.

If the great Khan's tale is embellished, mythologized, and sometimes just plain made up, that's understandable in a people that still seem a little uncomfortable in the trappings of a modern nation-state. And for this, the country's complex and often savage 20th century must bear no small share of the blame.

As even a quick glance at Ulan Bator's glum architecture will reveal, today's Mongolia is in many ways a creation of the Soviet Union. Russia's Bolsheviks played an important part in establishing Mongolian independence, and their successors did their best to ensure that that independence was a sham. Ulan Bator (the name means "red hero") resembles a rundown provincial capital anywhere in the former USSR. Like many such cities, Ulan Bator was embellished with the occasional unconvincing local flourish (its wedding palace is built in the shape of a traditional Mongolian hat), but its true spirit was crushed. Most of Ulan Bator's monasteries were, like the monks who inhabited them, obliterated, their ornate forms replaced by the slovenly grandeur and gimcrack construction so typical of Soviet rule. Even the mausoleum of Mongolia's other great hero, the "red hero" himself, Damdiny Sukhbaatar, bears a suspicious resemblance to Lenin's in Moscow.

At least the statue of Stalin that stood outside the national library was finally pulled down, if only in 1990. Other, more disturbing, traces of the murderous Georgian still remain. In 2003, construction workers uncovered a mass grave containing the remains of perhaps a thousand people. Most of the victims were Buddhist monks, shot, bludgeoned, and dumped in a ravine near Khambyn Ovoo: a small portion of the tens of thousands of victims slaughtered, exiled, or imprisoned in the 1920s and 1930s as the Mongolian party leadership, carefully choreographed by Moscow, brought the grim drama then playing in the USSR to their own country. The script is familiar, complete in every disgusting detail, even down to the rise of Horoloogiin Choibalsan, a puppet Stalin all Mongolia's own.

There's an old wooden house in Ulan Bator that gives a flavor of those days. Once the residence of a Mongolian prime minister murdered in Moscow in 1937, it now hosts a museum dedicated to the victims, complete, as such museums usually are, with the incomplete: the names and the photographs of just a few of the dead. A wax tableau reproduces the scene in an interrogation chamber, while upstairs a small pile of skulls from the Khambyn ravine shows how such interrogations tended to conclude.

And as expected in the former Soviet empire, the accounting for the Communist years remains unfinished, ambiguous, and uncertain. A statue of Lenin presides over the prostitutes outside a downtown hotel, and Choibalsan still stands on his pedestal outside Ulan Bator's university. Choibalsan's party is in Mongolia's governing coalition and its candidate recently won the country's presidential elections. But the Mongolian People's Revolutionary party is not what it was. It has accepted democracy, the free market (more or less), and, even, alliance with the U.S.; the Mongols are back in Baghdad, if rather less bloodily than in the time of the khans. Ulan Bator may be desperately poor, but there are many outward signs of returning enterprise--bustling shops, sidewalk kiosks, even a stock exchange.

Outside Ulan Bator conditions are far tougher. For a couple of days our group stayed in a ger (yurt) camp in a high valley to the north. The valley was lovely, with more than a touch of Shangri-La about it, but even this idyll offered a glimpse of a very hardscrabble Arcadia, where few inhabitants had much in the way of, well, anything. Life in Mongolia is harsh: The climate is merciless, incomes are low, and with little in the way of infrastructure (there are, for example, probably fewer than 5,000 miles of paved road, a miserable figure for a country the size of Alaska) it's difficult to see how that will change any time soon. But if anyone can make this all work, I like to believe that it will be this tough, resilient people.

And before you say that this is a hopeless dream, go to the steppe and watch a lone horseman riding calmly through that vast impossible space, his herd in front of him, and history just behind.

Mr. Stuttaford is a contributing editor of National Review Online.