Victorio led the Warm Springs band of Apaches, known in Spanish as the Ojo Caliente or in their own tongue as the Chihenne. Their homeland lay north of present-day Monticello, New Mexico, in the Canada Alamosa, where a 1876 census counted 916 Apache men, women, and children living on their reservation. But the U.S. government pursued a policy of concentration, forcing all Apache bands onto the San Carlos Reservation in the Arizona desert. San Carlos was a death sentence disguised as policy: overcrowded, lacking grass for livestock or game to hunt, contaminated with bad water, and rampant with malaria, a disease previously unknown among the Apache. Colonel Edward Hatch and Lieutenant Charles Merritt of the 9th Cavalry, the African-American Buffalo Soldiers, petitioned Washington to let Victorio stay at Ojo Caliente. Washington refused.

Facing arrest on murder and horse theft charges in Silver City, Victorio fled the Mescalero Reservation on August 21, 1879, with approximately 80 warriors and their families. His chief lieutenants were his sister Lozen, a warrior in her own right, and Nana, already more than 70 years old but still formidable. Victorio never commanded more than 200 warriors, and rarely were they concentrated in one place. On September 4, returning to his homeland at Ojo Caliente, 40 of his men attacked a company of the 9th Cavalry, killing 5 soldiers and 3 civilians while capturing 68 horses and mules. A week later, near McEvers Ranch at Lake Valley, Victorio ambushed civilian volunteers searching for him, killing ten. The survivors reported an Apache force of 100 men.

September 18, 1879 brought the war's defining moment. Four companies of the 9th Cavalry, more than 100 Buffalo Soldiers, followed Victorio's trail into Las Animas Canyon in the Black Range. It was a trap. Victorio and 150 warriors held the heights above the canyon and pinned the soldiers down for the remainder of the day. First Sergeant John Denny carried Private A. Freeland to safety across four hundred yards of open ground while under fire; Lieutenant Matthias Day rescued another wounded soldier. Both would receive the Medal of Honor, though Day waited eleven years and Denny nearly sixteen for the recognition. The cavalry withdrew after dark, abandoning camp equipment to the Apache. The canyon would carry the name Massacre Canyon ever after.

The war sprawled across international borders. Victorio raided into Mexico, where a relief force of 35 Mexican civilians sent to find 18 missing searchers met the same fate: ambushed and killed, their antique weapons left where they fell because Victorio had better arms. The U.S. and Mexico began unprecedented cooperation to hunt him down. In April 1880, more than 500 soldiers attempted to encircle Victorio at Hembrillo Basin in the largest engagement of the war. He escaped. At Palomas Creek in May, Apache scouts achieved what soldiers could not: they surprised Victorio's camp and killed about 30 people before running out of ammunition. Victorio was wounded, his son Washington killed in a subsequent engagement. Still he fought on, crossing into Texas where Colonel Benjamin Grierson's 10th Cavalry blocked him from waterholes at Tinaja de las Palmas and Rattlesnake Springs.

By October 1880, Victorio had retreated into the Mexican desert, desperately short of ammunition and horses. He sent out raiding parties while he waited at a place called Tres Castillos. On October 14-15, a Mexican force of 250 men surrounded his camp and attacked. They killed 62 men and boys, including Victorio himself, along with 16 women and children, taking 68 prisoners. Only three Mexicans died. Author Dan Thrapp called it a massacre: Victorio had almost no ammunition to resist. His sister Lozen was among the few who escaped. Nana, leading a raiding party elsewhere, survived to continue the fight through 1881, earning Medals of Honor for the Buffalo Soldiers who faced him at Carrizo Canyon, Cuchillo Negro Creek, and Gavilan Canyon. But the war that bore Victorio's name ended in the desert of Chihuahua, where a man who only wanted to live in his homeland died defending a people who had nowhere left to go.