"So this is the part where you tell us we’re lost, right?" I leaned forward and asked Moussa, our perennially cheerful driver. I expected a denial, but none came. In fact, Moussa looked positively despondent.

"Oh." I said, collapsing back into my seat. Apparently we were indeed lost.

I gazed out the window of the Land Cruiser--the same dirty window I'd been looking out for the past two days. We were deep in the West African country of Niger, in the Sahel, the searing, flesh-colored semi-desert fringing the southern Sahara. The harmattan, the hot wind that whips across the desert, was blowing again, carrying a fine sand that leaves eyes stinging and skin raw. I hadn't bathed in three days. It was 105 degrees; the Toyota had no air-conditioning. You could boil an egg in my water bottle.

Eventually our entourage--four four-wheel-drive vehicles carrying 13 Americans, ranging in age from 29 to 67, and enough supplies for a 12-day journey--stopped at a roadside stall to drink tepid Coke and reconnoiter. We were searching for Pirogi, a friend of tour leader Irma Turtle, and his clan of Wodaabe. There was only one hitch--we didn't know quite where to find them. "They are nomads," Turtle reminded me when I inquired about probabilities. "They move every few days, and even they don't know where they'll stop until they get there."

The Wodaabe are one of the world's better-known but least visited African people. We'd all been intrigued by photographs of their flamboyant beauty pageants--pictures of dramatically decorated faces grimacing maniacally. After the rainy season, Wodaabe clans hold ruumes, costumed dances where clan members compete against each other in a kind of combination cultural event and mating ritual. Ruumes are dress rehearsals for larger gerewol festivals, where numerous clans gather to be judged on face, body, dancing ability and "charm." The one refreshingly emancipated difference between a Wodaabe gerewol and a Miss Universe pageant is that the contestants are men.

Hoping to see either a ruume or a gerewol, I had flown two days to reach Niger's capital, Niamey, from California. I met the rest of Irma Turtle's tour group there and, after a few hours of sleep, climbed into a Land Cruiser with three other exhausted strangers. There are no set dates for these festivals, which occur at various times from September to November. We had 12 days to find some Wodaabe and hope they were planning to dance.

Turtle is a former New York advertising exec who threw it in 12 years ago to found an adventure travel company, Turtle Tours. She looks much younger than her 52 years, and she somehow managed to maintain a level of personal hygiene and chic in the desert that escaped the rest of us. Each day she wore a different dress of gauzy African fabric and masses of ethnic jewelry.

It was an intimate but unstructured trip. The advance itinerary was merely an approximation. "That's West Africa," Turtle would say with an ethereal smile when moving from Plan C to Plan D or E, "and you'd better get used to it."

The first day, we drove east through Sahal grasslands to Tahoua, a shabby market town bordering the Sahel and edged by dunes. Numerous police blockades delayed us for long hours. Niger has had trouble with rebel Tuaregs, a nomadic Saharan people, and police detained all those heading to Tuareg country, making sure they weren't gun smugglers.

As we continued east, away from civilization, the terrain grew increasingly silent and stark. At the end of the second day, with night near, our lead driver pulled over to speak to a turbaned man on camelback. The rider squinted and waved a finger vaguely into the murky miles of featureless desert. At that moment, my spirits flagged. I was suddenly tired of being filthy, tired of being tired. How could we find a small band of nomads in this dark wasteland?

We veered off the road in the direction of the pointed finger and began driving over trackless stretches of sand, scrubby bush and sporadic acacia trees. Hours of dusk and darkness streamed by, until, miraculously, a fire flared on the horizon. We had found Pirogi's Wodaabe, miles from civilization and light years from home.

As we unfolded ourselves from the vehicles, lean silhouettes emerged from the gloom and moved into the campfire light. There was something almost spectral about them. They were tall and thin, with carved cheekbones, sloe eyes, blue-black lashes, lofty foreheads and razor-straight noses. The entire clan, about 30 people, drifted forward, one by one taking our hands lightly in both of theirs, whispering, "foma, foma, foma"--meaning, roughly: "Welcome, how are you, how is your family, your herd, your life?" They smelled of smoke and herbs, of warm skin and dust.

Their angular bodies were wrapped against the cold desert night in lengths of deep blue cotton. Sometimes when they moved, the cloth fell aside, exposing the naked shoulders of a Giacometti statue. Firelight dusted their faces with iridescence, copper on ebony.

Many of their faces were patterned with small, symmetrical, blue-colored scars, which had been incised with razor blades. Both men and women wore colorful glass beads and gris-gris, leather amulets to stave off evil spirits.

The Wodaabe consider themselves a chosen race of rare beauty. They are not a gregarious people, frowning on interracial marriage. The reason for our warm welcome was the two women accompanying us, Turtle, and American painter Leslie Clark. Turtle has spent months with the Wodaabe during the past eight years; Clark has traveled with her for the past three. They are regarded as mildly eccentric, much loved, overly nomadic members of the extended family. Both speak some Fulfulde, the language of the Wodaabe, few of whom speak either English or French (Niger's official language).

The encampment was scattered with igloo-shaped shelters, framed with branches and covered with woven mats, netting or fabric. Each open-air kitchen contained a tall wooden mortar and pestle for pulverizing millet, a caldron and stacks of intricately carved calabashes.

Our meals were usually something like goat stew, conjured by Hema, one of two cooks accompanying us. Our complicated meals must have been mind-boggling to the Wodaabe, who live on milk, ground millet, yogurt, sweet tea and occasionally the meat of a goat or sheep. But they were too polite to stare, wandering away whenever food appeared at our table.

Foam rubber pads and mosquito nets draped over iron bars driven into the sand were our accommodations. Each night with the Wodaabe, I fell asleep watching Orion pass overhead. Each dawn, I awoke to the braying of donkeys, the obscene, deep-throated gurgling of camels and the low hum of people drawing blue smoke from morning fires.

On our first night, the tribal head, Chief Tambari, asked whether the younger people could dance for us. Dancing is intrinsic to Wodaabe life. It's part sport, part entertainment and part courtship ritual. "This is who the Wodaabe are," Pirogi told us. "We are good herders and beautiful dancers."

The Wodaabe have a startling, almost supernatural ability to materialize out of the night. That's how the dancers appeared, slender figures raising their arms to the moon, feet stamping up a membrane of dust, hands clapping out the pulse of the music. Their songs were sonorous and thrumming, broken at times by a shrill "yeeee hooo" from one of the women.

Academics argue about the origin of the Wodaabe, but agree they are related to the Fulani, a cattle-herding people scattered throughout Central and West Africa. The Wodaabe themselves believe they are of Caucasian descent. If this is true, some anthropologists say, it is possible they crossed the Red Sea from Arabia.

There are currently 40,000 to 50,000 nomadic Wodaabe traversing the Sahel, moving on when their animals deplete the surrounding grasses.

They are technically Muslims, having adopted the dominant religion of the region. They neither drink alcohol nor smoke. They refer to God as Allah, but little else implies strict Islamic practice. Each man has between two to four wives, depending on his affluence and appearance. The Wodaabe are not wealthy. When they need cash to purchase supplies, they sell livestock, milk, butter and herbal medicines in places such as Agadez, a market town on the ancient trans-Saharan trade route.

Their traditional Sahal territory is coming under dispute by their aggressive neighbors to the north, the Tuaregs. Additionally, the Sahara continues to spread south, devouring the Sahel and blurring the boundary between Wodaabe and Tuareg domains.

Tourism is not yet a significant financial opportunity for the Wodaabe--they see foreigners once a year, if that--but they were happy to part with clothing and jewelry, which we bought and wore. Turtle also contributes to the tribal coffers with presents such as sugar and medicines.

I had brought small bottles of hand cream, shampoo and bars of soap to give the women, who walked away with these simple offerings, giggling, rubbing the cream into their skin and sniffing the strange scent.

The morning following the dance, I lay on my mattress and watched the women as they packed up to move. The only furniture in each shelter was an extravagantly large and elaborate wooden bed, which they disassembled and strapped to donkeys.

After milking the cows and bidding farewell, Pirogi's convoy loped off, casting stick-figure shadows on the sand. Small boys ran behind, herding the animals with piercing calls. The women rode donkeys or walked ahead, infants strapped to their backs.

We drove northeast, through Agadez, then south. This time we were seeking a Wodaabe chief named Gundi, a friend of Turtle's.

When we found him two days later, he was traveling with several families, about 60 people, who were engaged in daily ruumes. Turtle had arranged for us to spend several nights at their camp to witness these contests. By the camp was a large circular area, about half the size of a football field, that had been cleared of brush. This, Gundi explained, was where everyone would watch the first ruume that evening.

Typically, ruume and gerewol competitions are between young men who want to impress potential wives. Around 4 that afternoon, 19 of them gathered under a tree to prepare. They began by covering their faces with a yellow powder.

The makeup followed traditional patterns. On top of the yellow base, each man drew a white line down his nose and a pattern of dots on his cheeks, chin and forehead. Each blackened his lips and rimmed his eyes with finely ground charcoal. A tiny cracked mirror was passed around and lingered over.

Once done, the young men traded their robes for animal hide wraps and embroidered, open-sided tunics. They piled beads and gris-gris around their necks, strapped on long swords in intricate scabbards and donned either white turbans with tall ostrich plumes or traditional Fulani herder hats. The final accessory was a leather headband from which dangled beads, coins or cowrie shells to frame the face. When the sun dropped to the trees, they fell in a line and walked slowly into the clearing.

The men were narrow-waisted, long-limbed and eerily feminine. They had the air of catwalk models at a Paris fashion show: tall, elegant, lithe, flowing and dressed to kill.

Three attractive Wodaabe girls were brought forward as judges while the rest of the families and visitors watched quietly from the sidelines. The competitors began to sing and sidestep the yakke--a dance involving exaggerated facial expressions. Because whiteness of eyeballs and teeth is considered erotically appealing, the dancers crossed and rolled their eyes, exposing as much of the eyeball as possible. They grimaced widely and puckered the mouth, inflating their cheeks and uttering clicks and wails.

To display his height, each man stepped forward, rose on his tiptoes and swung his arms, while feverishly working his eyes and mouth. Several dancers seemed to enter a trance; their eyes bulged and their lips quivered as they sucked in air; their heads swiveled from side to side, sweat beading on yellow brows.

After several hours, night enveloped the arena and a fire was lighted. Without warning, the three pretty judges walked forward, hiding their faces behind scarves. They swung their arms almost imperceptibly in the direction of the man they thought the most handsome and graceful. The selection of the winner happened with such a surprising lack of suspense and pomp that I wondered if perhaps he always won. He was taller and more muscular than most. His face would be considered striking in almost any culture. He received no prize, just kudos, and the no-longer-demure attention of the young women. For the other men, there was always another night and another ruume to impress the judges and potential mates.

During a gerewol, Turtle said, the face paint is red rather than yellow and the torso is kept bare except for diagonal strands of white beads. The men are expected to dance day and night in a macho display of endurance. Apparently the female spectators at these events make for a brutal peanut gallery. The older women, in particular, delight in ridiculing any man who puts on a poor performance, looks ugly or collapses from the heat. Alternatively, if they think a dancer is a particularly fine specimen, they will approach with a wail and butt him with their heads. The younger women don't indulge in this behavior; they must act coy and retiring, at least until the dances are over.

Sexually, the Wodaabe are very liberal. Unmarried Wodaabe girls are permitted to have sex whenever and with whomever they wish. At gerewols, a disgruntled wife is also entitled to leave her husband and run off with a new contender, marrying him that same day if she can escape uncaught.

The ruume dancers in Gundi's camp continued well after the winner was chosen. At midnight, after they finally disbanded, Leslie Clark, Turtle and I heard more singing drifting in from the desert. Intrigued, we followed the voices in the darkness. Soon we came upon a group of five young men, still costumed, standing in a tight knot under a crescent moon. We stayed to one side, not knowing if we were crashing a male bonding session.

The men were performing the ruume, the men facing inward, shoulder to shoulder, clapping, chanting and shuffling sideways. Eventually, when about 15 men had wandered in to join the ruume, one dancer broke away and approached us, gently taking me by the hand and leading me into the circle.

My graceful partner, Jirma, tried to teach me the song lyrics. He held my hand during the breaks in the dance and blocked other men if they tried to step between us.

The forthright Wodaabe don't bother much with courtship. If a man wants to have sex with a girl, he simply asks by scratching her palm with his index finger. If she's willing, the couple disappears behind a bush.

Irma had warned the women in our group about "The Handshake." But I was still flustered when it came, stammering like a teenager. Apparently I should have considered myself lucky to solicit any offers at all. It was later explained that my blond hair was sort of a turnoff.

Jirma didn't seem bothered by my refusal. He gently pushed me back into the circle of dancers, drawing my body close to his, folding his fingers between mine. I breathed the scent of warm milk, tea, sage, earth and musk that rose from his skin.

I spent an hour or more under that hanging moon, a single tree sticking up against the sky, dancing in the vast African desert with a man who moved like a shadow. He had never seen the ocean, never been in a car, and I doubt he had ever had a drink with an ice cube in it. We had nothing in common. And yet I was sure about my own sense of ease and happiness.

When, eventually, I mimed that I must get some sleep, Jirma took off a string of beads and placed it around my neck. The beads were warm on my skin. His wrist rested on my shoulder.

"Baraka (blessings)," he said, "baraka, baraka."