EVEN BY THE EXTREME standards of Afghanistan—a country where a majority of the population has never known peace and the average life expectancy is 43 years—the province of Badakhshan, which contains the Wakhan Corridor, is a rough place. One telling measure is the number of women who die during pregnancy. In the U.S., the rate is 11 per 100,000. In Afghanistan, it soars to 1,800, and the situation in Badakhshan is as bad as anywhere in the country.

It's also the only part of Afghanistan that was never conquered by the Taliban. Credit for that goes to some exceptionally tough local mujahedeen commanders, one of whom has just surrounded our plane with a dozen heavily armed men and several pickup trucks. Wohid Khan, 52, has dense black eyebrows and a precisely razored beard that's just starting to turn gray. He started fighting the Russians at age 22; these days he's in charge of border security in the eastern part of the province. Khan and 250 men patrol 840 miles of rugged terrain where the Wakhan shares a border with Pakistan, Tajikistan, and China. This is one of the most heavily trafficked heroin routes in the world, as well as a popular thoroughfare for gunrunners.

Like many mujahedeen whose schooling was cut short by war, Khan sees education as the key to reversing Afghanistan's devastation—which is why he has given his full support to Mortenson's projects. The father of several daughters, he's especially passionate about building schools for girls. As a gesture of respect, Khan will provide Mortenson with a high-speed escort in three Ford Ranger pickups, rigs that carry shoulder-held rocket launchers and a .50-caliber machine gun mounted to a tripod.

We roar out of Faizabad, with three soldiers perched in the back of each truck, their Kalashnikovs between their knees. As we barrel along on unpaved roads, Mortenson explains that this is not his standard mode of travel.

"When Sarfraz and I come into the Wakhan, we're usually in a beat-up jeep or a minivan that we've hired, and we're constantly switching drivers to avoid getting ambushed or kidnapped," he says. Sarfraz also switches up languages while concocting elaborate lies about who they are and where they're going.

"When I'm worried, there is no stopping, no eating, no drinking," Sarfraz says. "Greg's life is very important to me."

Traveling with Wohid Khan is different: Since he's the local strongman, the only thing you have to worry about is hanging on. Khan's drivers are under orders to push their rigs to the maximum speeds that the shattered roads allow—40 to 50 miles per hour. Moving fast is standard procedure, because the border-security force handles all sorts of problems over a huge area. Two weeks ago, a car transporting two teachers, both of their wives, and four children to a new CAI school in the village of Buzzai Gumbad accidentally shot off the road into the Amu Darya River. The driver and one of the families were drowned. The other family spent the night balanced on the roof of the car. Khan and his team raced to them the next morning and pulled the survivors to safety.

Khan can be quite ruthless about keeping these roads open, which is crucial for the flow of food supplies to the region. This becomes evident one afternoon when we encounter a truck that has obstructed traffic by stopping in the middle of the throughway. The commander gets out and walks up to a man who's working on a broken rear wheel.

"Driver or mechanic?" he asks.

"Driver," the man replies.

Khan smashes his fist into the man's face, then kicks him in the stomach, twice. He gets back in the Ranger and we resume our journey.

"People criticize me for working with so-called warlords," says Mortenson, "but sometimes you're forced to choose between working with the resources at hand and not accomplishing anything at all. In the end, it's all about relationships, and we're willing to collaborate with almost anyone who shares our commitment to education."

For the next two days, we bash though dry washes and small villages, pushing deeper into the most obscure corner of Afghanistan. When we reach Baharak, the valley forks in three directions and we head west toward Ishkoshem, a town of 20,000 families. Here, on the morning of our third day out, we come to the jewel of the CAI's Wakhan program: an unfinished foundation about the size of a football field, filled with dirt, stones, and loose sand, future home of the Ishkoshem Girls' High School.

The completed structure will be two stories tall and will host 1,200 female students. Costing more than $70,000, it will be the largest school ever built in this region, and it will have one of the most magnificent settings for any school anywhere. To the north loom the Pamir Mountains, painted with the shadows of high clouds, racing across the brown slopes in the lemon-yellow light. To the south are the sharper ridgelines and cliff faces of the Hindu Kush, armored in ice even now, in late July.

He glances briefly over at Khan, who listens carefully. "A wise man in this area once told me that these mountains have seen far too much killing, and that each rock you see represents a mujahedeen who died fighting either the Russians or the Taliban. But now that the fighting is finished, it is time to build a new era of peace. And the first step is to take up these stones and start turning them into schools."

The applause from Khan and his soldiers is especially fierce.