In 1892, a Comanche war party descends on the homestead of Wesley Quaid and his family. Quaid (Scott Shepherd) is killed, as his wife and three children attempt to escape. All three children are hit and killed by gunfire as the family runs away. Quaid's wife, Rosalie (Rosamund Pike), runs into the woods and hides, still holding onto the youngest child, a baby, who is dead. The Comanches search briefly for her, but fail to find her.
In nearby Fort Berringer, New Mexico, Captain Joseph Blocker (Christian Bale) and his men captures an escaped Apache family and brings them back to the fort. Later he has a drink with old friend Master Sergeant Thomas Metz (Rory Cochrane). Metz is weary from his long years of service and says he is done soldiering. He has had his guns taken from him after a diagnosis of "melancholia." The men recount battles they have fought and friends they have lost.
In the morning, Captain Blocker is called to the office of Colonel Abraham Biggs (Stephen Lang). Biggs informs Blocker that the President has ordered that Cheyenne war chief Yellow Hawk (Wes Studi), who is dying from cancer, and his family be released so that they can return to their ancestral lands, Valley of the Bears, in Montana. Captain Blocker is told that it will be his duty to escort them and make sure that they get there safely. Initially, Blocker refuses the Colonel's order, even when faced with a court-martial, recounting terrible things that he has personally witnessed Yellow Hawk do. Blocker also exchanges words with Jeremiah Wilks (Bill Camp), an East Coast journalist who is also in the room, when Wilks points out that the Captain has also done some horrible things to natives. The Colonel warns Captain Blocker, who is set to retire, that his pension is at risk if he refuses his duty, and so Blocker reluctantly agrees. He is given papers signed by President Benjamin Harrison that will guarantee safe passage.
Block sets out with a party that consists of Chief Yellow Hawk and his family (his grown son Black Hawk, Black Hawk's wife Elk Woman, Yellow Hawk's daughter Living Woman, as well as Black Hawk's young son Little Bear) and a small band of soldiers: Corporal Woodson (a Buffalo Soldier), Lieutenant Kidder (a West Point graduate), Master Sergeant Metz (who gets his guns back) , and Private Philippe DeJardin (a young Frenchman).
The party sets out from Fort Berringer. Once away from the fort, Captain Blocker stops their progress and gets down off his horse with a knife in hand. One of his fellow soldiers hands him a second knife. Blocker orders Yellow Hawk to come down off his horse in his native tongue. Yellow Hawk complies, and Blocker offers the old man one of the knives. The Chief refuses the offered knife. Blocker then orders that the Chief and his son be put in chains for the duration of the trip and he orders the women's braids be untied.
Further on their journey, the group comes across the burned-out home of the Quaid family. Blocker, Metz, and Woodson leave the group behind to investigate. They see Quaid's body still lying in the spot where he was killed and scalped. Inside the house, they find Rosalie, still holding her dead infant and sitting near a bed where her daughters are lying covered by blankets, also clearly dead. She warns the soldiers to be quiet because the children are "sleeping."
Blocker and his soldiers go along with it, taking the "sleeping" children and her husband back to the group. Blocker tells some of his men to get shovels to dig a hole, and to get Rosalie a clean blanket for her infant. She gets angry when one of the soldiers approaches her, telling him not to touch her child. She seems to come to terms with the fact that her children are, in fact, dead; however, she insists that she will dig her family's graves. She attempts to do so, starting by hand, but fails. She allows the soldiers to dig the graves instead and makes Blocker promise to bury her with her family. After the camp is asleep Rosalie steals a pistol and goes out to the grave site but Blocker follows and takes away the pistol.
Later that night, one of the native women offers Rosalie clean clothes, them being covered in the child's blood, saying she would be honored if Rosalie would wear them. Rosalie accepts. Meanwhile, Captain Blocker is warned by Yellow Hawk and his son that the Comanche will keep following them and that they are all in danger because the Comanche will not discriminate between the white men and the natives. They want Blocker to unchain them so that they can help defend the group if they are attacked, but Blocker refuses.
The next day the group are attacked by the Comanche. During the battle Private DeJardin is killed and Corporal Woodson is badly wounded. The Cheyenne men help during the battle, riding over an attacker and Black Hawk chokes one with his chains. The Comanche who haven't been killed in the battle ride off. The group watches as Rosalie picks up a pistol and repeatedly shoots a dead Comanche until the pistol runs out of bullets.
After making camp that night, Blocker orders the native men's chains to be taken off. During the night Master Sergeant Metz relieves Lieutenant Kidder of guard duty. The two men talk briefly. Kidder says that the Comanche he killed in battle was the first man he had ever killed. Metz recounts the first time he killed a man, at 14 years of age when he was fighting for "the Grays" (a.k.a. the Confederate Army). He says that after killing for a while, it gets easier and doesn't mean anything. Kidder says that that's what he's afraid of.
The next day the group comes upon the remaining three Comanches, who have been slaughtered. Captain Blocker deduces that it was Yellow Hawk and Black Hawk, who must have slipped out of camp in the night and tracked them down and murdered them. He is upset with Metz for allowing them to slip away.
The group arrives at an army Fort in Colorado, where the wounded Woodson is turned over for medical treatment. Blocker and Rosalie have dinner at the home of Lieutenant Colonel McGowan and his wife, Minnie. Mrs. McGowan, apparently unaware of what has happened to Rosalie, goes on about the poor treatment of natives by white men. Her husband angrily quiets her. Blocker asks McGowan if Rosalie can stay with them until she can find passage to wherever she may wish to go. McGowan agrees but lets them know that the stage isn't running and Rosalie may have to stay with them until Christmas, as there will be no one traveling through until then. McGowan asks Blocker to do him a favor. He would like for Blocker to make a stop along the way to drop off disgraced Sgt. Charles Wills at his home base. Wills has killed a family with an ax and is being returned to be hanged for murder. Blocker agrees but doesn't know the Sergeant's name.
In the morning, Captain Blocker visits a recovering Corporal Woodson. Woodson is upset because he thinks he has let Blocker down, but Blocker assures him that he has never let anyone down, and tells him that is father would be proud of him. They say goodbye for what they acknowledge will likely be the last time.
As the party gets ready to leave, with the condemned Sgt. Wills and two news escorts, Corporal Thomas and Sergeant Malloy, in tow, Rosalie asks Blocker if she can continue with him instead of staying in Colorado. He agrees. Rosalie, having been supplied with fresh clothes gives Elk Woman back the clothes she had been offered shortly after joining the group. Sargeant Wills and Blocker recognize each other before they ride out.
Later, the group makes camp for the night. Wills is chained to a tree. He talks with Blocker and recalls that Blocker did many things that he could easily have been punished for. Later, Rosalie and the two native women are kidnapped by a group of fur traders who come across them as they wash dishes at a creek. Alerted by Little Bear, Blocker and several of his men, as well as Yellow Hawk and Black Hawk, track them down. They find the fur traders' camp and witness one of the kidnappers beating Yellow Hawk's daughter. When the kidnappers return to their tents, the men sneak down into the camp and attack the kidnappers in their tents and kill them. One of the rescuers is killed in the struggle.
Later, Rosalie convinces Blocker to sleep in his tent which she has been occupying during a downpour. Metz intrudes on the conversation and Blockers talks with him. Metz expresses that he is leaving, after which he goes to Yellow Hawk's tent, offering the man some tobacco as a gesture of redemption. Still later, Wills, who has been left out in the rain, feigns a coughing fit to coax Lieutenant Kidder into unchaining him. Wills attacks Kidder, eventually getting control of his pistol and shooting him dead. The gunshot awakens the camp, and Blocker shoots Wills as the man escapes on a horse. Metz jumps on a horse and gives chase. In the morning the group finds the two men's bodies. Metz has a bullet to the head and is holding the bloody gun. The group bury Metz but Blocker refuses to bury Wills.
As the group finally reaches Montana, Blocker and Yellow Hawk, who is near death from the cancer, speak. Blocker names some of the men he had lost fighting Yellow Hawk. Yellow Hawk responds by saying that he had also lost people. The two men shake hands in an apparent mutual act of forgiveness and friendship.
When they arrive at Valley of the Bears, they bury the now dead Yellow Hawk using a traditional native burial scaffold. An older man and three younger men arrive on horse. The older man informs Blocker that he owns the land they are on and that the younger men are his sons. He says that he wants Blocker and his party to all leave, and to take Yellow Hawk's body with them. Blocker attempts to show him the papers signed by the President, but the man is uninterested and gives a dire warning. Rosalie points a rifle at the old man. The man says that he doesn't think she has what it takes to pull the trigger, at which point she shoots and kills him. The man's sons, the soldiers and Black Hawk exchange fire. In the firefight Black Hawk, Elk Woman and Living Woman are all killed, as is Corporal Thomas. Two of the younger assailants are also dead, but one tries to limp away. Blocker shots him in the back and then walks up to him and uses a knife to dispatch him.
Later, Blocker, Rosalie, and Little Bear stand on a train platform all dressed in new civilian clothes. Rosalie is set to board a train to Chicago, taking Little Bear, now an orphan, with her. She says goodbye to Blocker, tells him he is a good man, and boards the train with the young boy. Blocker begins to walk away, but turns back and, after some consideration, steps aboard the train as it leaves the station.