[2] As was the custom, he became the leader of a large mixed band of Mimbreños and Mescaleros (led by his friend – and probably brother-in-law as the husband of another daughter of Mangas Coloradas, as well the same Cochise – Caballero) and fought against the United States Army.

Victorio and his followers (including Nana, Nana's Mescalero wife, and San Juan) left the reservation twice, seeking and temporarily obtaining hospitality in Fort Stanton Reservation among their Sierra Blanca and Sacramento Mescalero allies, before they came back to Ojo Caliente only to leave permanently in late August 1879, which started Victorio's War.

Victorio was successful at raiding and evading capture by the military and won a significant engagement at Las Animas Canyon in what is now the Aldo Leopold Wilderness on September 18, 1879.

However, Victorio continued his campaign with the attack on Fort Tularosa, where his warriors had to face a detachment (K troop) of the 9th Cavalry and were repulsed by the "Buffalo Soldiers" after a harsh fight.

[3] Victorio's camp near the Rio Palomas, in the Black Range, was surprised and attacked on May 23–25, 1880, but the Mimbreños and Mescaleros succeeded in repulsing the soldiers.

[8][9] A memorial statue of Victorio riding a horse is located in the city of Chihuahua, Mexico, as a recognition to the N’nee (Chiricahua) and Apache peoples.