In New Mexico Territory, Apache chief Cochise has forged a firm and peaceful friendship with Major Jim Colton, commander of Fort Buchanan. One day, Cochise and his pregnant wife Nona visit the fort, and Colton explains to Cochise that many soldiers are leaving the fort to fight in the Civil War in the East. Colton promises to stay in the Southwest near his Apache friends. Soon after, Neil Baylor, a government Indian agent, arrives with an untrustworthy scout named Mescal Jack and announces that reinforcements will be brought in to deal with the Indian problem. Much to Colton's anger, Baylor expresses his intent to move the Apaches to the San Carlos reservation away from the Butterfield Overland route, a stagecoach pass, even though peace treaties granting them land rights have already been signed. A short time later, a Butterfield Overland stagecoach bound for Tucson is attacked by Geronimo, chief of the Mogollon Apaches, and all the women and children are mutilated. Colton and Baylor go to see Cochise, and Baylor declares that if the killers are not found, the Chiricahua, Cochise's Apache tribe, will be sent to San Carlos. Cochise responds that his tribe will not leave their lands, but that at the Indian's council he will vote to send the bad Apaches away from the area. At the council, Geronimo tries to persuade the Chiricahua to fight the whites, but the council chiefs vote to banish him. When Cochise tells Geronimo and his men that they must leave behind Mary Kearney, a young schoolteacher whom the renegades kidnapped at the time of the Butterfield stage massacre, another brave, Niga, challenges him to fight for her. Cochise wins the battle, and Nona thinks that he is in love with the white girl. Cochise assures Nona that he only has eyes for her, and then brings Mary to Fort Buchanan, telling Colton that she would make a good wife. Meanwhile, Baylor and Mescal meet with Geronimo, and offer to sell him guns and ammunition in exchange for raiding a ranch and making it look as if Cochise were responsible. Geronimo agrees, kills the rancher's wife, kidnaps his son, and leaves behind the emblem of Cochise's tribe, a thunderbird pendant. While Colton is away investigating the attack, Baylor approaches Lt. George Bascom and says he will be promoted if he can get the kidnapped boy back from Cochise. At the meeting between Cochise and Bascom, Cochise tells Bascom that Geronimo perpetrated the attack, but Bascom accuses him of lying, and as he is about to arrest him, Cochise escapes. Bascom takes Nona and three braves hostage. Sgt. Reuben Bernard, Colton's ally, demands that he release Nona, but Bascom insists that the three hostages will not be released until the boy and the guilty Indians are turned over. Cochise takes a military man hostage, and when Bascom calls him a liar, he kills him. In retaliation, Bascom hangs the three braves, one of whom is Little Elk, Cochise's brother. Cochise and the Chiricahuas go into mourning and then vow to avenge the deaths of their braves by joining forces with Geronimo and declaring war on the whites. Meanwhile, Colton returns and learns from Bernard that Baylor masterminded the conflict between Cochise and Bascom. He arrests Bascom just as the Indians attack. Mescal goes to Cochise and says that troops are arriving to drive the villagers from their lands. Cochise accuses him of lying and has him shot. Eventually, Colton decides to abandon Fort Buchanan, and the entire population of the fort, including Mary, moves to Fort Sheridan. As the wagon train travels through Apache Pass, the Indian warriors, including Cochise, watch from the rocks above and then shoot. Baylor is shot, and then runs to the Indians claiming to be their friend, but Geronimo kills him. Colton and Bernard decide that they must use cannons in order to win the battle, and when they begin to shell the area, the warriors scatter. Cochise finds Nona, who has been injured, and then approaches the wagon train in order to get medical attention from Dr. Carter. Geronimo tells the remaining braves that Cochise is no longer their leader as he only thinks of his squaw, and then he attacks. Cochise rides with a white flag to Geronimo, who challenges Cochise to a fight to the death. Cochise wins but decides not to kill Geronimo, declaring instead that he is an outcast and no longer an Apache warrior. Later, Nona gives birth to a boy, and then gives Mary, who has cared for her, a bracelet that will protect her from Apaches. Mary and Nona say goodbye, and Cochise and Colton, who is in love with Mary, agree to speak again about peace sometime soon.