"If you're going to compete in traditionally red states as a Democrat, if you're going to expand the electoral map, then you're going to have to compete in places where native voices are of some considerable significance," says Keith Harper, a member of the Cherokee Nation who serves as the chair of Obama's Native American Policy Committee. "From time to time has a Democratic candidate opened an office on a reservation? Yes. But we have native outreach directors in numerous states. Before, it was hit or miss, little bit here, little bit there. Right now it's a comprehensive effort."

One of Obama's signature promises during the primary was that he could expand the electoral map for Democrats. And the Obama campaign sees an opening to do so in several reliably red states in the American West that have sizable Native American populations. Native Americans make up only about 1 percent of the population in the crucial swing states of Nevada and Colorado. But they're a significant presence in North Dakota (4.8 percent) and Montana (6.4 percent). And Indian country comprises nearly 10 percent of the population of New Mexico, which George W. Bush won by only a few thousand votes in 2004.

"Within many of these western states, particularly those who have over the last couple decades elected Republicans, one of the ways in which Democrats have been competitive is to ensure that they have been responsive to tribal communities," Harper says. "Democrats who have made a concerted effort to reach out to Indian country have solidified their base."

Mary Bowannie, a lecturer in Native American studies at the University of New Mexico who teaches a course called "The Native Vote," says she's noticed the Obama campaign has placed more of an emphasis on Native American voters than past Democratic candidates. "There's really been a push to get out the vote in Native American communities," she says. "There's a lot of participation and excitement. When [John] Kerry ran, he had people on the ground, but it was very much focused on getting the tribal leadership behind them. They did have some focus on community and getting out the vote, but not as much as they have recently."

It seems that the Obama campaign may be making its move for the Indian vote at just the right time, too. George Hardeen, the communications director for Navajo Nation President Joe Shirley Jr., who has endorsed Obama, says that Navajos appear to be paying more attention to politics this year than ever before: "Access to information in a place as geographically isolated as the Navajo Nation is as great as it ever has been, and that alone has moved the message in. So even traditional Navajo people like my mother-in-law, who speaks no English...she knows who Obama is, and she knows who John McCain is. They're not watching Fox and CNN, but they are forming opinions."

Next page: One race in particular exemplifies this bloc's ability to determine an election...

For observers of Native American politics, one race in particular exemplifies this bloc's ability to determine an election. Late on election night in 2002, Sen. Tim Johnson (D-S.D.) was losing, with only a few counties left to report. It was already a banner election year for Republicans, who would finish the night having regained control of the Senate and expanded their majority in the House. Among the last votes to come in that night were from the Pine Ridge Sioux Indian Reservation, which includes Shannon County, the least white, most Native American, and second-poorest county in America. State Democrats' ambitious get-out-the-vote campaign had increased turnout among the state's Native Americans by more than 70 percent.

When all the votes were counted, more than 90 percent of Shannon County went for Johnson, who won by 524 votes over John Thune. (Republicans would later claim, falsely, that "phony Indian votes" stole the election for Johnson.)

"We swung that election," says Garriott. "And it was a huge win that reverberated around the nation. Since that time, there's been a lot more attention paid to the Indian vote."

Indian country has also been credited with delivering Montana to Bill Clinton in 1992 and a Senate seat for Democrat Maria Cantwell in Washington in 2000. In 2006, Montana Democrat Jon Tester unseated incumbent Conrad Burns due in part to vastly increased Native American turnout.

As Garriott notes, Indians' effectiveness as a voting bloc has traditionally been limited because Native Americans register to vote at far lower rates than the general population. So if the Democrats need Indian country to win in the West, they're also going to need to raise registration rates.

In concert with its outreach program, the Obama campaign began soliciting endorsements from tribal leaders as early as January 2007. It has thus far received public support from more than 100 tribal leaders and more than 20 tribes. Despite representing a state with no federally recognized tribes, Obama has put together a far-reaching Indian policy platform, calling for a White House senior adviser on Indian issues and a yearly "Tribal G8," which would bring leaders of different Indian nations together in Washington to meet with the president and help fashion the federal government's Native American policy agenda.

Sam Deloria, a long-time advocate of Native American causes, says endorsements are all well and good, but he's glad campaigns are no longer just focusing on tribal leaders. "Getting the tribal leadership to endorse you doesn't mean that they're going to put together a get-out-the-vote machine for you at their own expense," says Deloria, a lifelong independent. Both parties are starting to realize, he says, "If you want the votes, you're going to have to go out and get them."

So what about John McCain? If any Republican could have a shot at the Native American vote, it's the Arizona senator. McCain represents a state with 20 federally recognized tribes and is a former chair of the Senate Indian Affairs committee, where he oversaw the investigation that put Jack Abramoff in jail for defrauding the Native American tribes that were his clients. Hardeen, the Navajo president's spokesman, says McCain has a long history of maintaining good relationships with tribes. When Hardeen was a reporter, McCain spoke to him briefly about his relationship with tribes. "He told me his proudest moment in politics was receiving the endorsement of every Arizona tribe when he ran for reelection in the Senate. That's how well he was respected by tribes then," Hardeen says.

But for McCain the problem of history remains. Native Americans are traditionally Democratic voters, so he is automatically at a disadvantage when trying to convince a poor, rural population with scant access to information to back him. In many traditional homes (known as "hogans") in Navajo country, it's common to see pictures of John F. Kennedy. "I can't explain why John Kennedy resonated with traditional Navajo people going back all the way to the early '60s," Hardeen says. But he did. And Obama is poised to benefit from that.

On Thursday, the AP reported John McCain was drastically cutting his ad spending in Colorado. New Mexico has looked out of reach for the Republicans for some time. Kalyn Free, the head of the Indigenous Democratic Network, an organization that focuses on recruiting Native American candidates and mobilizing Indian voters, doesn't think it's over yet. But she's confident of one thing: "The next president of the United States will not win the White House without the Indian vote. We've come a long way."