Navajo Mountain, a large laccolithic dome, straddles the Utah-Arizona border of the Navajo Indian Reservation. The Navajo call this sacred mountain Naatsis'aan, "Head of the Earth Woman." Navajo Mountain has a rich and varied historical past. The earliest maps identify it as Sierra Panoche. The ruined dwellings and irrigation ditches of Desha and Anasazi people, evidence of years of human occupation, still stand on nearby mesa tops, canyon walls, and desert floors.

Official documentation of the occupation of Navajo Mountain began with Spanish explorers and Catholic fathers Anastasio Dominguez and Silvestre Velez de Escalante, who "met only Paiutes" when they forded the Colorado River near Navajo Mountain in 1776. The San Juan Paiutes and Navajos occupied the surrounding mesas and rugged canyons in the early 1800s.

The Paiutes had friendly relations with both Navajos and Utes (traditional enemies of the Navajos), and frequently served as a bridge between the two. They began losing their traditional lands between Navajo Mountain and Kayenta in 1884. Over the years, the Navajo succeeded in getting Paiute holdings added to their reservation. In the 1980s, the Paiutes asked to be recognized as a distinct Indian tribe.

A number of people have found refuge in the isolated canyons surrounding Navajo Mountain. In 1859 Mormon pioneer Jacob Hamblin found safety in Spaneshanks's camp south of Navajo Mountain, after a party of four Navajos had killed George A. Smith. Hashkeniini evaded Kit Carson's army troops with a party of seventeen men, women, and children, finding sanctuary near the mountain. In 1892 Chach'osh settled at Navajo Mountain after shooting Mormon Lot Smith near Tuba City for killing sheep belonging to his relatives.

A number of white men visited Navajo Mountain in the 1880s. Rumors of Hashkeniinii's secret silver mine attracted miners, the best-known being Cass Hite. Hashkeniini refused to tell Hite the location of the silver mine but did tell him where he could find gold on the Colorado River. In 1884 a heliograph station was placed on Navajo Mountain by U.S. troops under a Captain Thomas.

The discovery of nearby Rainbow Bridge by white men created controversy over whether John Wetherill, Byron Cummings, or W.B. Douglass saw or reached the bridge first. A number of amateur and professional archaeologists surveyed Navajo Mountain; they included John Wetherill, Earl Morris, Ralph Beals, Neil Judd, J. Walter Fewkes, Harold S. Gladwin, A.B. Kidder, Byron Cummings, and Charles L. Bernheimer. In 1960 and in 1981 Alexander J. Lindsay and Richard Ambler excavated sites near Glen Canyon and the northeast portion of Rainbow Plateau for Northern Arizona University.

The Rainbow Lodge and Trading Post were built in 1924 by S.I. Richardson and his son Cecil. A second post, a tent operation located near War God Springs, was operated on the other side of the mountain by Ben and Myri Wetherill. In 1932 the Dunn family from Chilchinbito established the Navajo Mountain Trading Post near Cottonwood Wash; it was sold by Dunn's daughter Madelaine Cameron in 1978.

In the 1930s, Navajo Mountain children attended school in a tent using empty explosive boxes donated by the Civilian Conservation Corps for desks. In 1936 the school took over the buildings once occupied by an American Indian Rights Organization field nurse. Though a number of teachers served at the hogan-style boarding school, the most famous was Lisbeth Bonnell Eubanks. During her tenure, the day school became a boarding school for kindergarten and first grade students. With donated food and money, she kept the school operating during World War II and pioneered new methods of teaching bilingual students. A new stucco/adobe, red-roofed boarding school was built in 1982 near Rainbow City, a housing development northeast of Navajo Mountain, for kindergarten through eighth grade.

Trader S.I. Richardson claimed the road he built in 1924 from Red Lake to Navajo Mountain followed an ancient "Ute War Trail." The road was bitterly opposed by rival traders and their Navajo allies from Shonto and Kayenta. In the 1930s local men hired by the CCC rebuilt and shortened sections of the road. Additional improvements and an extension to Paiute Mesa followed in 1960. In 1988 the Navajo tribal government began paving sections of the road. Anglo acculturation is discreetly traveling down this road in the beds of wagons and pickup trucks.