Magdalena Gilkeson (Blanchett) is a widowed frontier woman living on her ranch in 1885 New Mexico with her two young daughters, Lily (Evan Rachel Wood) and Dot (Jenna Boyd). Life isn't easy, but they make the most of it with Maggie's live-in lover, Brake Baldwin (Aaron Eckhart). One day a mysterious man named Samuel Jones (Jones) comes dressed like an Apache Indian, seeking shelter. Maggie gives him a bed and supper, but is otherwise cold towards him—recognizing that he is the father who had abandoned her and their family when she was young, and blaming him for her mother and brother dying without him being there to help. When Maggie and Dot discover their ranch hand and Brake brutally murdered in the nearby woods the next day, and Lily missing, they find out that a band of renegade Chiricahua men led by Pesh-Chidin (Eric Schweig), nicknamed El Brujo, kidnapping girls to sell as sex slaves are responsible. Maggie is forced to put her feelings aside and accept her father's help to rescue Lily.
- The Cameo: Val Kilmer as the unhelpful U.S. Army Cavalry officer.
- Cruel and Unusual Death: It is not said how it was done, but Brake's head is stuck in a bundle of animal skins hanging over a fire. All we know is that Dot heard him screaming, so possibly being skinned or dismembered alive.
- A large bag like that over a fire also implies boiling to death.
- Damsel in Distress: Lily, Kayitah's son's bride, and many other young women are captured by sex trafficking murderers who plan to drop them off in Mexico to be sold.
- Deliberate Values Dissonance: The racism the whites and Indians showed each other was pretty realistic given the setting.
- Slavery was common practice to the Apache. Several other tribes including the Haida, Pawnee, Cherokee, and Comanche did as well.
- Defiant Captive: Lily tries to fight in her own ways once she's captured, once getting herself beaten for running back to the cave to grab the sick toddler the men were going to abandon, and another time attempting to escape.
- Disappeared Dad: The reason Maggie is so angry with Samuel.
- Go-Go Enslavement: Modest by modern standards, but the kidnappers have Lily and the other girls wear "lipstick" and very dressy clothes to look more appealing to the future customers looking to buy them as sex slaves.
- Hair of Gold, Heart of Gold: The Gilkeson women, all three of them, though Lily can come off slightly as a Jerk with a Heart of Gold sometimes.
- Magical Native American: Samuel's old friend Kayitah. The villain, Pesh-Chidin, is this too, but a witch who uses his magic to harm. Samuel himself is white, but when he was accepted into the Chicahua culture, he became this as well.
- Maybe Magic, Maybe Mundane: El Brujo's major uses of magic throughout the movie such as Maggie getting sick after he curses her and melting a man's eyes with a handful of powder could easily be explained as bad luck/timing and treated herbs/fungi respectively, but there's never a definite answer either way.
- Rape as Backstory: Inferred that Maggie's first daughter Lily is a Child by Rape.
- The Savage Indian: Pesh - Chidin and the rest of his men.
- Interestingly, Pesh-Chidin is seen as this by other Indians. They're equally disgusted and fearful of him and it's noted that he has to run with renegades because no tribe or clan will take him in. A great example of Shown Their Work: in the culture of the South-West Nations, "skinwalkers" like him were seen more as demons inhabiting bodies than actual human beings.
- To the Pain: Pesh-Chidin gives an utterly chilling one to Lily after she defies him once too often.El Brujo: [as he pours sand down Lily's throat and forces her to swallow] This is what the rest of your life will taste like.