In 1853, shortly after the end of the war between Mexico and the United States, Apache and Comanche Indians are stepping up their attacks on Mexican ranchers living in the Tucson area. In the hope of putting an end to the Indian raids, Cavalry General Gadsden sends Major Burke to the territory to make peace. Before Burke leaves, Gadsden warns him that the Apache warriors, under the leadership of Cochise, are ferocious fighters. In Tucson, Burke meets town leader Sam Maddock, but is unaware that Maddock is the instigator of trouble between the Indians and the settlers, and that he is forcing the Mexicans out of their homes and taking their land. One Mexican, Felipe, the son-in-law of landowner Don Francisco De Cordova, is especially embittered by the Indian raids, having lost his wife to an Apache arrow. Felipe is equally suspicious of the Americans, who he believes are also interested in taking the Mexicans' land. When Burke is invited to dine at Don Francisco's hacienda, he meets the beautiful Consuelo, Don Francisco's daughter. The visit is interrupted, however, by the unexpected arrival of Cochise. After Cochise and Burke discuss the Cavalry's presence, Cochise leaves vowing to remain at peace with the Americans. Running Cougar, the renegade Comanche leader, rejects the peace agreement, and leads a bloody raid on Don Francisco's hacienda. Cochise and his men arrive in time to save the hacienda, and Running Cougar is killed. Angered by the killing of his brother, the once-peaceful Red Knife announces that he will no longer abide by the peace treaty, even if it means war with the Apaches. Fearing a war with the Comanches, the other Apaches side with Running Cougar, and decide to join the fight against the whites. Realizing that his people are no longer interested in the treaty, Cochise and his wife Terua go to Tucson to meet with Burke. Maddock, meanwhile, conspires with Felipe to kill Cochise, but Felipe accidentally kills Terua instead. Cochise finds the rifle that was used to kill his wife, but before assuming that it was an American who killed her, he decides to give Burke a chance to prove otherwise. Cochise sends a raiding party to Tucson to find a hostage who will be used to force Burke to visit them. In Tucson, the raiding party kills Maddock before abducting Consuelo. Soon after Burke arrives at the camp, he is given four days to prove that the Americans were not responsible for the death of Terua, or face war. While in captivity, Consuelo falls in love with Cochise, who takes her to a romantic place in the wilderness. Back in Tucson, Burke discovers that the rifle used to murder Terua belonged to Corporal Carter, who admits that he got drunk one night and left it at Maddock's saloon. Tracing the rifle to Felipe, Burke wrings a confession from him and takes him to Cochise. The war dance is called off; however, Felipe, who remains unrepentant, makes another unsuccessful attempt to kill Cochise. Felipe is then killed by one of the Apaches. Cochise goes to Red Knife to persuade him to call off the war, but Red Knife refuses to accept Cochise's story and orders his death. Burke and his men arrive in time to save Cochise, and with the help of Apaches who are loyal to Cochise, the Comanches are defeated. Consuelo wishes to remain with Cochise as his wife, but the Apache leader refuses to let her "live the life of a renegade" and insists that she leave with Burke. Consuelo accepts Cochise's wishes and leaves with the hope that the bloodshed has ended.