I didn't know anyone who'd been to this place. I could hardly find it on a map. But the Crimean Peninsula, on Ukraine's Black Sea coast, has been Russia's favorite beach resort for nearly two centuries, a haven for aristocrats whose quaint afflictions – consumption, hysteria, heartbreak – were thought to be cured by warm baths, mellow sunlight, and lungfuls of dry air. The tubercular Chekhov lived in Yalta, whose palm-lined pavilion is featured in his famous story "Lady with the Lapdog." Later the Soviets built state-sponsored coastal sanatoriums so that proles too could get a dose of sunshine.

We'd been walking toward the Black Sea for five days, along the craggy Crimean Mountains, and now and then the forest would fall away and we'd spot the sea shimmering in the distance. Buttresses of limestone launched toward the water, and tucked into the sea cliffs ahead we could see Sudak, the first major town on our route, heralded in one guidebook as a quaint pre-Soviet village near a huge grotto and vineyards renowned for their champagne. I was already thirsty.

I was tagging along with a commercial trek led by Mountain Travel Sobek, a California-based outfitter that runs adventure tours in exotic places. The plan was to walk six days through the mountains, then another five along the coast. Trip leader Rob Smurr, a mountaineer and professor of Russian history, is the kind of guide who takes as much joy in a place's oddities as in its postcard moments. This trek along the Crimean coast was not advertised in the company's catalog but was marketed online and to returning customers, presumably those with a high tolerance for the unexpected.

The degree to which "Trekking in Ukraine's Crimean Jewel" would be exploratory was not clear until I had flown to Kiev, shuttled across town to an overnight train for Simferopol, and was rocking along in the dining car with Rob, drinking beer and eating what would be the first of many meals of soggy mashed potatoes and boiled sausages of unspecified origin. Rob is 46 years old but looks a lot younger, with the blond beard of a mountaineer and close-cropped hair left over from his two decades in the U.S. Army. He speaks Russian, German, and Estonian and worked as a State Department translator in Russia and Finland. Looking out the window at the flat expanses of plains offset by the grim outlines of rusted factories, I asked him what the terrain would be like where we were going.

"I don't know," he said, grinning and swigging his beer. "I've never been there."

As it turned out, Crimea looked a lot like my native California, before we wrecked it with highways, mansions, and smog. Along the rocky spine of the Crimean Mountains, where a high plateau collides against the sea, it was gorgeous: rolling grassy hills, jagged stone outcroppings, and deep, shady forests. It felt like the hills of Malibu a hundred years ago, unspoiled by, well, Californians. From the dusty trails in the high chaparral, the sheer cliffs and jeweled waters around Sudak beckoned me sweetly.

But then we got there. Sudak turned out to be a carnival-slash-nightmare: fun-house mirrors and miniature-horse rides, slot machines and disco balls everywhere you looked, Casio lounge singers and photo booths in which you could dress up like a Tatar. After dark Rob and I picked a route between boardwalk shacks that hawked seashells and beach towels. On a nightclub balcony a dancer with platinum cornrows and silver go-go boots gyrated in the flicker of red, white, and blue neon. Across the street a bar band was mangling an old Creedence song: "I want to know," the singer croaked with a heavy accent, "can you ever seen some rain?"

We watched, speechless. Suddenly Rob smiled broadly. "In America," he said, "I'd do everything in my power to avoid coming to a boardwalk like this. But now I travel halfway across the world and end up staying here."Growing up during the Cold War, I only knew Ukraine existed from playing Risk (said to be George W. Bush's favorite board game in college). In the game, Ukraine was the giant country comprising the entire eastern flank of Europe, a strategically important territory. To the east lay equally exotic Risk territories such as Ural, Siberia, Kamchatka, and Yakutsk. These places were mysterious and inscrutable – and since the 1920s they had all been part of the USSR.

Although significantly smaller than how it appeared on the Risk board, Ukraine is now an independent country – the second-largest in Europe, in fact. But while some parts of the former Soviet bloc – Prague and the rest of the Czech Republic, especially – opened immediately to the West, others warmed up more slowly, partly because of their continued domination by Russia. As a result, many Americans' knowledge of Ukraine can be summed up in one word: Chernobyl, site of history's deadliest nuclear meltdown, in 1986.

A lot has happened since then. After languishing in Russia's shadow for decades, even after the fall of communism, Ukraine burst into the world spotlight in 2004, when its massive Orange Revolution upended the corrupt Russian-backed regime that had ruled the place since the Soviet collapse. After a presidential election marred by fraud, hundreds of thousands of Ukrainians took to the streets in support of the opposition candidate, Viktor Yuschenko, a popular, pro-Western politician who survived poisoning, allegedly at the hands of his political rivals. The Russian-backed candidate was eventually defeated, and Ukraine erupted in celebration of its first truly elected government in a long time.

The capital city, Kiev, Europe's seventh-largest, was already a town on the make, flooded with American and Western European businessmen jockeying for advantage in the post-Soviet market, and the Orange Revolution cranked it a gear higher. In the bustling streets shiny cars dart between Parisian-style townhouses and golden-domed cathedrals as the famously gorgeous Ukrainian women clack their Prada heels on the winding cobblestone streets. (A cursory Google search of "Ukraine Women" suggests that one of the country's leading lures for Western businessmen is something euphemistically referred to as "romance tours.")

The attraction is mutual. Although America is more hated abroad now than at any point in its 230-year history, over in the former Evil Empire – where they are fawning over their newfound liberty like a child unwrapping a pellet gun under the Christmas tree – the natives actually seem to like us. At least one forward-thinking firm has cashed in on the pro-Western mood by introducing a popular new beer, called Hike, in an orange can, the color of the revolution. "Freedom is your way," the label declares in English, at once capturing the moment's plucky optimism and also, perhaps, betraying a Borat-like misread of the West it is trying to imitate.

Signs of westernization disappeared once we left Kiev, and so did the rusted-out Soviet-era factories dotting the plains. I soon forgot that I'd chosen to go hiking in a country most famous for a toxic disaster. On our first night in Crimea we camped above a run-down vineyard overlooking the sea, and at sunset we were serenaded by farmers in the back of a flatbed, bumping over a dirt road, calling their hogs. Shucks to your global economy: Down here, when you buy a bottle of Hike at the local market, the babushka rings you up on an abacus.

There were 12 in our group: Rob, photographer Andrew McGarry, and me, as well as four clients who had presumably already tasted Rob's brand of freewheeling exploration. Our Russian coordinator was Gia Ksnelashvili, a 41-year-old native of Georgia who lives in St. Petersburg and works for one of Russia's oldest outdoor outfitters. A veteran mountain guide, Gia has climbed Europe's tallest mountain, 18,510-foot Mount Elbrus, 61 times. Most of his clients are Westerners (he knew Rob and three of the Sobek clients from a previous trek in Georgia), and as a result he has learned to speak very good English. For this trip Gia had contracted a small army of local outfitters: a guide, a cook, a driver, and a helper.

We began the next morning by hiking from our camp in the vineyard into the Valley of the Ghosts, a steep limestone ravine studded with flat-topped Crimean pines that looked like overgrown bonsais. Eagles and ravens soared overhead. Our local guide was Sergei Kalinin, a 55-year-old former mechanical engineer; since Soviet times he's been leading hikes, which had long been his passion. Sergei had black shaggy hair, glasses that darkened in the sun, and a stoic, weathered face. Every now and then he would point at a tree with his walking stick and sheepishly tell us something in Russian, knowing that unless Rob or Gia was nearby to translate, we wouldn't understand a word. Somehow we managed to get the gist. We reached the top of the ravine and peeked over a ridge, where bright yellow hollyhocks swayed in the wind and, far below, the sun skittered over the sea.

By the time we reached our destination, after plodding through a shabby village with a small church on the outskirts, the crew had already set up camp; they'd made their way via backroads in a groaning old bus, a squat blue cupcake that did its best to euthanize its occupants with clouds of diesel smoke and carbon monoxide. Valiery, the driver, was a stocky middle-aged man whose wrinkled forehead gave him a look of constant amusement. He smoked cigarettes and poured out shots of honey vodka while the others prepared dinner. Olga, the cook, a bubbly 18-year-old too young to remember communism, worked as a beautician most of the year and wore Calvin Klein T-shirts. She was chopping potatoes and shredding cabbage with the help of Roman, a 20-year-old college student who wore full camo fatigues all the time.

The next day we crossed a green plateau broken up by limestone benches, then dropped into a thick deciduous forest where ferns and mushrooms sprang from the ground and springs bubbled up into stone troughs. We rappelled into a chilly cavern in which ice clung to the walls all year. We came across a series of seldom-visited war memorials engraved with the hammer and sickle, honoring Stalin's troops who resisted the Nazis in World War II. Sergei had done this route more times than he could count, and he breezed from trail to road to doubletrack without ever consulting a map.

As we traversed the mountains we ran into only a handful of other hikers, all of them Russian or Ukrainian. Sergei told us that a pair of Canadians did one of his Crimean treks, but as far as he knew we were the first Americans. Indeed, eco-tourism has made little headway here. We came across two young soldiers dozing in the afternoon shade of a lone cypress tree on the side of a narrow jeep road, purporting to monitor some clunky tin boxes sprouting antennae that looked like leftovers from World War II. They said that artillery practice was underway and advised us not to walk on the road. So Sergei led us through the grass about 100 yards to the side of the road, which didn't strike me as much safer.

Despite all the cultural gaps, a few days in the woods brought out some essential similarities between us and our hosts. On our final night in the mountains Valiery built a big fire; once it had burned down to coals he erected a small grill and covered it with skewers of cubed pork. "There are three things a man can watch forever," he said, grinning. "River running, fire burning, and another man working."

He sat on a stump by the fire and meticulously drizzled the shashlik with a vinegar marinade. (Earlier he had tried one of the folding camp chairs and immediately crushed it. "But they're guaranteed to 90 kilos," said Gia. "Ha!" said Valiery. "I weigh 120.") The grilled pork was tender and tangy. After dinner we sat around the fire with a guitar, swapping cowboy laments and Russian folk songs. Valiery broke out the vodka and we all took shots, chasing them with small slabs of salo, a Ukrainian delicacy that is essentially raw bacon fat. When Valiery produced a second bottle I crawled off to my tent. When I awoke hours later with a bad headache, I could hear the others still laughing and drinking and telling stories.Rob seems continually surprised at just where life has delivered him, or what it has delivered him from. One evening we stood in the wind watching the sunlight dance across the sea. Piñon and juniper trees clung to the rocky slopes. "Just think: Turkey is only 150 miles away," Rob said. "Another 200 miles, and you're in Iraq."

If things had turned out differently, Rob might've been on the far side of Turkey. With his background in military intelligence, he was one of a precious few army reservists who spoke four languages, let alone held a Ph.D., but with the war in Iraq spreading the armed forces thin, he would have been just another grunt with a gun. He thought the war was a blunder, but that wasn't the worst of it. "I knew that some kid who would probably flunk my class would have the legal authority to order me to charge a machine gun nest," he told me. "No, thanks." So in 2005 he left the army after 22 years and continued teaching history at Washington's Evergreen State College.

Today the Black Sea is clearly more peaceful than the Persian Gulf, but in fact it's been fought over for more than 200 years. In 1788 Catherine the Great hired naval hero John Paul Jones to help defend her newly acquired Crimean beachfront from the Turks. Between 1854 and 1856 the Russians faced off against an alliance of British, French, and Turkish forces. More than 200,000 were killed, but no territory traded hands, and in the end there was no decisive victor. The Crimean War may have been forgotten altogether if not for its famous literary spawn. On the British side Tennyson immortalized the bloodshed in The Charge of the Light Brigade; Russians learned about the full horror of the war largely from a little-known aristocrat whose battlefield writings gave him the reputation as the first war correspondent. "I failed to become a general in the army," Leo Tolstoy later said, "but I became one in literature."

During World War II blood flowed again in Crimea as the Russians repelled the Nazis in a series of furious battles. Sevastopol became the headquarters of the Soviet navy, and Yalta gained fame for the 1945 Big Three Conference between Franklin Roosevelt, Winston Churchill, and Joseph Stalin. Crimea's hills have been peaceful for the past six decades; the only reminder of its bloody past are the war memorials.

Although Ukraine swells with nationalist pride, Crimea remains a pro-Russian outpost. Many Crimeans winced in 1954 when Soviet Premier Nikita Khrushchev transferred Crimea from Russia to Ukraine. Since all Soviet republics were ruled by Moscow, the transfer was largely symbolic, but now that Ukraine is independent there's some bitterness in Crimea about being part of Ukraine. Most of our crew all considered themselves Russian, no matter what their passports said. The peninsula even keeps a separate parliament. But so far Crimea showed no signs of becoming another Chechnya.Despite the sideshow horror of Sudak, it was easy to see why the Crimean coast has been so prized. Walking along the spectacular cliffs, we stopped for lunch where the tide rose over barnacled boulders and swam out into the cool green pools. We continued hiking toward a windblown cape with a crumbling lighthouse; clear emerald water lapped at pebble beaches in pocket coves below.

One day Andrew and I rode in the bus to photograph the crew, so we arrived at the tiny beach resort of Morskoye a few hours before the others. It was like Atlantic City gone to seed. Trash was scattered everywhere on the beach: plastic beer bottles and heaps of rotting watermelon rinds, moldy sneakers and garbage bags stuffed full of picnic leftovers. Tinny synth-pop blasting from a cafe was like the soundtrack of someone's struggle with insanity. Graffiti scrawled on a cement wall along the boardwalk translated as a warning that litterers would be fined. Looming over it all was the orb-shaped concrete husk of a luxury hotel, abandoned after the Soviet Union fell. An idle crane poked toward the sky. It looked like the Death Star.

Valiery parked the bus on what we would come to call Dysentery Beach, where scraps of toilet paper fluttered in the wind like prayer flags. A stinking outhouse induced the gag reflex at a distance of 20 feet. Nevertheless Olga and Roman began to unload the bus. Well, here we are, they seemed to say, motioning at us to come along and start enjoying camp. They looked happy to be sharing the beauty of their country.

Andrew and I, groggy from the bus fumes, just smushed our noses against the window and peered out at a murky creek trickling over waterlogged grocery sacks. He and I were accustomed to sketchy roadside bivys, but even we agreed that if we were to come upon this beach late at night, needing a place to crash, we would just keep rolling. As for the paying clients whose arrival was imminent, they were doctors and investment bankers who came to Crimea equipped with UV-blocking hiking pants with zip-off legs, not haz-mat suits. Such world travelers might brave Himalayan blizzards and alligator-infested rapids, but there was no chance they were going to sleep next to someone else's shit. My meager Russian was not nearly up to the task of tactfully explaining this to the busy Crimean crew, so I pitched my tent amid the garbage, crawled inside, and popped open a cold bottle of Hike.

Rob, Gia, and the others arrived at Dysentery Beach a little while later, and the look of disappointment – horror, really – on their faces was memorable. "Is this the camp?" asked someone, hesitantly. It was. After a sullen dinner, eaten on folding chairs in the shadow of the Death Star, Rob averted mutiny by loading us into the smoking blue cupcake bus and checking us into a hotel.

"In Soviet times there were more regulations, and people followed the rules," Sergei told us, removing his glasses and rubbing his eyes. "But now it is like anarchy."When Americans travel abroad, we always yearn to discover "unspoiled" places, such as mythical Tuscan villages or tiny Caribbean islands unsullied by other American tourists. But here's the thing about the Crimean coast: It was spoiled when we found it. Two centuries of Slavic-style tourism had done some damage.

But then again, who was I to be self-righteous? Sure, the stinking trash heaps on the beach were a bummer, but ultimately they would be a lot easier to remedy than the refineries and freeways that blight the coast of California. And more to the point: The Ukrainians have just cast off the shackles of almost a century of dictatorship. Let them throw a little trash.

The funny thing about freedom is that once people get the idea they've been liberated, they start acting as if they're free – at which point, well, maybe they are. So go ahead, drive your Lada onto the beach, slip into your banana hammock, start a bonfire, take a dump in the sand, crank up the techno, and chuck your bottles down the beach. One definition of freedom is simply breaking the rules and doing whatever the hell you want. All we needed were some yahoos revving up jet skis and firing guns, and it would be just like spring break on the "Redneck Riviera," the Florida Panhandle.

Just as in America, the lazy tourists crowded the most accessible places on the Crimean coast, while the backcountry offered sanctuary for the seekers. On our final day we stumbled upon a scene farther east that reminded me of the American desert or Baja California, Mexico. Here, on a less spectacular and less crowded beach called Fox Bay, where muddy brown cliffs collapse on a desolate shore, the beachgoers were younger, thinner, and better-looking than the porcine bathers around Morskoye and Sudak. On this beach the tents were permanent, palapas of palm branches and plastic sheets strung between Russian olive trees along the base of the crumbling bluffs, the only shade on the entire stretch. The women were tanned and nude, the men wore sarongs, and naked babies scurried underfoot. A gorgeous naked woman scrubbed laundry in a plastic tub while a man with a long beard stuffed his pack with empty plastic water jugs and headed down the beach to find a place to refill them. At the nearest road head someone had put an old van up on blocks and was working on the tranny. I got the feeling that in Fox Bay they were ready to wait out the apocalypse, or maybe they thought it had already come and didn't care; they'd found their paradise.

Has freedom really come to Ukraine? It's hard to say. President Yuschenko's reformist party has been assailed as corrupt and incompetent. And the old Russian-backed party won the recent parliamentary elections, which means Yuschenko now works directly with the man who was his rival in 2004. Business as usual, it seems.

But as I walked along a dusty two-track, where a pair of loose cows rummaged through a trash pile, I suddenly felt elated. As surely as governments will misgovern and leaders will mislead, there will also always be havens like this where the dreamers sink beneath the surveillance and soak up the sun's democratic warmth. Freedom is our way, after all, and freedom is what we may yet find.

Plan Your Expedition

Decades of Soviet rule left the Crimean Peninsula and its surrounding areas relatively unexplored by Westerners, so you're forgiven if you don't immediately associate Ukraine, southern Russia, and Georgia with world-class hiking, skiing, and mountain biking. But trust us, they're there. Here are four trips to get you started.

Ride Crimea
The Meganom bike club offers weeklong fat-tire tours of Crimea's rugged southern coast. You'll camp on the Black Sea and explore a 15th-century Tatar palace. [$300-$600; meganom.info]

Explore the Ukraine
Mountain Travel Sobek no longer offers trips to the Ukraine, but the luxury outfitter Cox & Kings has picked up where they left off. The "Treasures of the Ukraine" package takes travelers through Crimea, Yalta, and Kiev. [from $2,767; coxandkings.co.uk]

Ski Europe's Top Peak
Just on the Russian side of the Caucasus, 18,510-foot Mount Elbrus is the fifth-highest of the seven summits. Seattle-based Mountain Madness gets you down the volcanic massif on ski or snowboard. [$5,375; mountainmadness.com]