John McCain hadn't been elected to the U.S. Senate when a fellow veteran and friend spotted him at the annual Navajo Nation Fair.
"Someone should tell this representative that he's only a representative ... this is not even his district," former Navajo Chairman and President Peterson Zah recalls his dad jokingly telling McCain.
That began Zah's friendship with the late McCain, who served one term in the U.S. House before becoming one of Arizona's longest-serving senators.
The Republican McCain helped usher through Congress some of the most pivotal legislation in Indian Country, including the right for tribes to open casinos. That legacy also includes criticism for seemingly favoring corporate interests over tribes.
At a memorial service in Phoenix days after McCain died from a brain tumor last month, tribal leaders from around Arizona gathered to pay their respects. A Navajo flutist was among the musical performers.
"There are a few that really advance the cause of Native Americans," said Delbert Ray, president of the Salt River Pima-Maricopa Indian Community. "But I'd have to say he's the bus driver."
Fresh to Washington, D.C., McCain relied on the late Rep. Morris Udall of Arizona and Sen. Daniel Inouye of Hawaii, both Democrats, to familiarize himself with Native American issues. Inouye later asked McCain to join him as vice chairman on what is now the Senate Indian Affairs Committee. McCain went on to serve twice as the panel's chairman.
McCain and Inouye believed solutions for long-standing problems in Indian Country didn't lie in the nation's capital, but rather with tribes, said Eric Eberhard, who worked for McCain for six years. McCain saw treaties with tribes as proof that the U.S. hadn't lived up to its ideals.
"He spent considerable capital trying to correct that when there was no political reward for it," Eberhard said.
In his last speech to the National Congress of American Indians, McCain said: "We must listen more to you, and get out of the way of tribal authority."
McCain helped write the Indian Gaming Regulatory Act of 1988 that established a legal framework for tribes to operate casinos on their reservations after a U.S. Supreme Court decision cleared the way. Now, nearly 240 tribes operate casinos in more than half of U.S. states, generating more than $31 billion a year in gross revenue.
McCain, Inouye and Udall also teamed up to enact the Native American Graves and Repatriation Act to ensure human remains and funerary items are returned to tribes. He worked on legislation to strengthen tribal self-determination and self-governance. More recently, he championed a bill to expand a child abduction alert system into Indian Country.
Zah introduced many other Native American leaders to McCain over the years, emphasizing his reputation and ability to work across party lines.
"In basketball, if the score is 90-90 with five seconds left, who do you go to?" Zah said. "The Indian people went to Sen. McCain."
Wendsler Nosie Sr., a former San Carlos Apache chairman, said McCain also missed opportunities to do right by Indian Country and is hopeful others in Congress can learn from that.
Nosie was flying back from Washington, D.C., in late 2014 when he heard McCain had slipped a provision into the national defense bill to give land Apaches considered sacred to a copper mining company. McCain touted the jobs it would bring, while Nosie and others decried the environmental and psychological damage they said it would cause.
"He pulled the rug from underneath us without anybody knowing anything," Nosie said.
Another provision McCain slipped into a must-pass bill earlier in his career allowed the University of Arizona to build telescopes atop Mount Graham in southern Arizona, another area Apaches considered sacred. They lost a legal battle to stop construction.
On the Navajo and Hopi reservations, the disdain some had for McCain stemmed from a massive relocation of tribal members and water rights.
McCain and Jon Kyl, who was named this week to temporarily fill McCain's seat, introduced legislation in 2012 to settle the Navajo and Hopi claims to the Little Colorado River. Much of the opposition came from the rushed nature of the bill and language in it to benefit a coal-fired power plant on the Navajo Nation.
"I don't know if he (McCain) did not understand but he advocated for corporate interests against our tribal aboriginal rights," said former Hopi Chairman Ben Nuvamsa.
Nicole Horseherder, a Navajo water rights advocate, said Navajo should be included in the compact that divvied up Colorado River water among Western states. She said McCain worked to keep tribal resources to a minimum.
"For him or anyone to say they are giving tribes what they want or consulting or ensuring, that's all baloney," she said.
In a statement after McCain's death, Navajo President Russell Begaye said the senator "sometimes had a rocky relationship with the Navajo Nation, but he was always willing to listen."
That included hearing about a painful part of Navajo history that resulted in thousands of tribal members being removed from Hopi land to settle a long-standing dispute.
McCain wasn't part of the legislation that put relocation into motion but repeatedly pushed for an office tasked with providing benefits to close. The fiscal conservative said the office far outlived its life and cost taxpayers millions more than it should have. The Hopis agreed but the Navajos did not.
Zah, whose tenure was dominated by relocation, said McCain was blamed unjustly for the troubles of those who were relocated.
Peter Osetek ran a legal services clinic for Navajos and Hopis in the 1980s and showed McCain around an area known as the Bennett Freeze, where a federal construction ban prevented Navajos from making fixes to their homes as part of the land dispute.
He said McCain saw one home dug into the side of a hill with a piece of wood for a door and said the conditions were "worse than the tiger cages when he was in Vietnam."
