In the fabled land of Genghis Khan where nomads still walk the earth, lies a huge, blue lake. We wanted to paddle the waters and experience this wild land first hand.

Dark shadows of birds whirled above the water, their soft songs filling the nighttime air. Not used to hearing birds at night, I awoke and crawled from my tent to find the source of this mysterious music. The full moon of a few days before had faded into near nothingness, letting the Milky Way shine like a glowing white river flowing across the sky. To the north, the jagged Sayan mountain range marking the northern border of Mongolia, was little more than a dim outline against the stars.

My two friends and I were camped on the northern shore of Mongolia's Lake Hovsgol. At 80 miles long, 22 miles wide and over 700 feet deep, it is the fourteenth largest freshwater lake in the world. A week earlier we'd set out in our sea kayaks to become the first people in the world to circumnavigate this remote body of water.

The adventure had come about randomly—one of us hear rumors of a big, remote lake in Central Asia—a place locals call the "dark blue pearl," saying it was the most beautiful spots in an unknown part of the world. A few phone calls later we found it tucked away in a corner of Mongolia.

There is almost nothing better than sitting with good friends, enjoying a good buzz and knowing that a challenging, wild adventure lies in your future.

My partners in adventure were two beautiful Australian women, Rosie and Jen, who I met while working in Hong Kong. We'd all been working in the crazy city for over a year, so visions of open water, mountains and the legends of Genghis Khan quickly flew through our heads. While sitting in a crowded Hong Kong cafŽ, the thought of spending time in open places and experiencing a nomadic culture sounded too good to resist. A few beers later we had equipment lists scribbled down and a departure date set.

There is almost nothing better than sitting with good friends, enjoying a good buzz and knowing that a challenging, wild adventure lies in your future. We sat drinking and laughing, our eyes shining with the promise of paddling a part of the world that most people still don't know exists.

Lake Hovsgol lies about 440 miles northwest of Mongolia's capital city of Ulaan Bataar. The lake is the centerpiece of the Lake Hovsgol National Park, an area set aside for protection in 1992 with funding from the United Nations Development Program. Often compared to Siberia's larger Lake Baikal, Hovsgol has escaped most of the environmental problems plaguing Baikal and remains on of the most intact ecosystems and purest bodies of water in the world. You can still drink straight from the lake with no ill effects.

In addition to the lake, the 838,000 hectare park also includes vast tracts of high mountains, taiga forests and forest steppes that harbor 244 species of birds, 750 species of plants and 68 species of mammals, including wolves, brown bear and reindeer. Natives that live near the lake remain equally diverse, with four distinct ethnic groups (Khalkh, Buryat, Darkhat and Tsaatan) living in and migrating through the area. The northwest corner of the park also remains one of the last areas where the dwindling Tsaatan population (reindeer hersdmen) continue their nomadic lifestyle.

Lake Hovsgol National Park represents a new era in Mongolian history. In 1921, Mongolia became the second communist country in the world after allying with Russia to drive out the hostile forces of a Chinese warlord who had taken over the capital city. From 1921 to 1990 Mongolia stayed intimately tied to the Soviet Union and the country remained off-limits to everyone but those from Eastern Bloc nations. When the Soviet Union collapsed, Mongolia was thrown headfirst into the world's economic and political arena, where it was left to fend on its own.

Protests, democratization and the initial steps toward establishing a market economy soon followed. This radical transformation continues to cause problems for Mongols, but it has also opened the country to foreigners. For the first time in 70 years, nearly anyone can now travel to Mongolia—fabled land of nomadic horsemen, Attila the Hun and Genghis Khan.

We started our trip in the dusty village of Hatgal on the southern shore of Lake Hovsgol and we immediately felt like we'd traveled back in time. The few streets were empty, except for a couple of villagers dressed in long traditional coats called dels, riding their horse around town on errands—much like we'd ride a bike to the store for milk.

A sense of quiet filled the air though signs of the Soviet era still littered the town—half-completed buildings, faded propaganda posters showing men wielding wrenches, robust women holding a baby in each arm. At one point someone installed streetlights along the main road. Today they are battered, the light sockets empty and the wires cut down and sold as scrap—signs of a bygone era in a land turning back to its roots to regain its identity. Today locals have turned from Soviet subsidies to tourism and count on the national park to boost the economy.

Since only a narrow finger of the lake drops down into Hatgal, we could not get a feel for the lake's size from town. Once we paddled just a few miles up the mountainous western shore, the lake opened up and looked more like an ocean. For Mongols, the "dark blue pearl" represents a place of national pride. We soon discovered the reason for the name. As soon as the sun slid behind the cloud, the whole lake changed from green and blue to an ominous gray. In the sun the water along the shore rivals the colors of the Caribbean, but the deep water always remains a mysterious blue.