The movie starts out with the explanation of the relationship between Virgil Cole (Ed Harris), the gunman/lawman for hire and Everett Hitch (Viggo Mortensen), a west point grad who decided that the army wasn't for him and he needed to discover himself in the wild, wild west. Everett had helped out Virgil once in a gunfight and since then, the two had been inseparable, with Everett taking second fiddle to the infamous Virgil. They're gunmen who only shoot when it's legal aka: When they're hired to be lawmen for towns that seem to have too many bad guys.
Cut to Randall Bragg (Jeremy Irons), a man in the town of Appaloosa who is trying to control the copper mines that have been discovered with his huge bunch of cronies. They also terrorize the town and implement their own rules. The current sheriff and two deputies come to his ranch to arrest two of Bragg's men, but Bragg takes matters into his own hands and kills all three of them with a young ranch hand (Joe Whitfield played by Gabriel Marantz) watching on in horror.
So the city fathers meet with Virgil and Everett and accept Virgil's rules of the road: my way or the highway, no discussion or I'll shoot you. It doesn't take but a few minutes and there's a disruption in a bar with two of Bragg's men urinating on the floor. Virgil and Everett wander on over and tell them that they need to stop, or head to jail. They don't stop, nor do they want to head to jail, and Virgil kills the two at the bar while Everett takes care of a third that appears out of a side room.
A day passes and Bragg and all his men come into town and meet with Virgil and Everett in a small bar. Bragg offers some way of reconciliation with Virgil, but as the last Marshall/sheriff was Virgil's friend, he has none of it. It ends with a tense standoff and Virgil telling them that they can't even bring weapons into the town now.
Enter Allison French (Renee Zellweger), fresh off a train with only a dollar to her name. Everett spots her first and follows her to a small restaurant where Virgil is also having breakfast. Both men seem to want to court her, but Everett gives way to Virgil, who seems smitten. Once he declares himself the city Marshall, Allison smiles and flirts. In turn, Virgil promises her a gig at the local hotel where if she plays the piano, she can probably stay for free (which is the only work available as she says she isn't a whore.)
Back at the law office, Everett and Virgil talk about Allie (what she likes to be called) a little, with Everett egging on Virgil just a bit, but obviously letting (and encouraging) Virgil to pursue Allie. They then see some riders on top of a hill that overlooks Appaloosa and decide to go and investigate. When they get up there, they have a mild confrontation that involves Virgil whacking one man with the butt of his pistol to make a point that Bragg has no power anywhere, inside or outside of the town.
A random bar scene is inserted to show Virgil's nasty temper when he beats the snot out of a rowdy man and Everett has to control him. The beating was unprovoked and it continues the line that is hinted at that Virgil is a simple man, not very educated and single minded. When he gets stressed, he goes and beats things up and is uncontrollable (but he doesn't often get stressed.) Later Everett had to apologize to the man and give him some liquor. When a town father asks him why Virgil doesn't do it, Everett explains that that isn't Virgil and if they want the town protected, they'll have to take the good and the bad, as they hired the man.
A day or a week or more is implied to have passed and during breakfast, Allie comes down with Virgil (obviously they just slept together) and announce that Virgil is going to be making her a house in town and they'll live there together. Everett is obviously surprised and midly upset that his friend hadn't told him, but congratulates them and says nothing. Breakfast is interrupted when Joe Whitfield comes in and says that he saw the killings and will testify. They cross examine him and make sure the kid is up for the task and when it appears that he is, head out to get Bragg. They catch him in the outdoor privy and drag him back at gunpoint into town through his angry (but obedient) men. Now comes the round the clock guarding of Bragg, who unfortunately has a cell right next to Joe and makes some threats that shake the younger man up.
Meanwhile, Allie's house is slowly getting built. Virgil doesn't know how to handle some of her requests and sends Everett over to deal with her a little. When Everett gets there, Allie corners him and kisses him, but after a few seconds of enjoying it, pushes her off and tells her that when they are not together, they're both with Virgil. Allie, obviously stung, asks him to leave. Everett says nothing about it to Virgil, but does to the hispanic prostitute he's been visiting and she tells him that eventually Allie will tell Virgil and he should be prepared for the 'not-nice' spin Allie will put on it.
Two other lawmen come into the office and offer their help to protect the prisoner and Virgil thanks them and agrees. Right before the judge is due to come into town, the Shelton brothers (Mackie and Ring) come into town. They're very good hired guns. Virgil knows them and unlike him, they go out for hire. After a small discussion, Virgil makes it clear who is in charge and the two brothers go into the hotel after watching Virgil and Allie go out for picnic in a carriage.
The judge finally comes and while all the Bragg boys testify for him, the damning evidence is presented by Joe and even Bragg's loquacious oratory that comes afterwards doesn't save him. The boy is told to get on his horse and run to the next town for safety and the judge orders Bragg hanged in another city (taken by train.) As the sentence is handed down, Bragg makes eye contact with the Shelton brothers.
On the train things seem to be going quietly, but soon it stops for a refill of coal and the Shelton brothers appear on a dry riverbed under the train and show they have Allie tied to a horse. They threaten to kill her if they don't release Bragg. Virgil agonizes for a few minutes and then gives up Bragg, but per the agreement, doesn't get Allie until they decide to release her. Virgil starts getting angry and goes after them on foot while Everett goes back to town via the train to get horses.
They meet up again after a day after Virgil has quieted down and catch up to the party. They see a bunch of Indians coming towards the other four and then Everett and Virgil see Allie frolicking in a river naked with one of the brothers. Both appear distressed, but more concerned about the Indians about to ambush the four people. The Indians do ambush them and Virgil and Everett fight them off, killing one of the Indian's horses in the process. Virgil then makes a deal with the brothers that they all will put aside differences until they're out of ambush range, after that they'll settle them. When Virgil and Everett are on guard duty, Allie comes up and sits between them, saying how scared she was and how it was a mistake. When Virgil asks Everett if he thinks that she'd sleep around again, Everett replies that "Allie needs a man." Allie then tries to say that Everett touched her, but when Virgil asks Everett, he denies that it happened like Allie says. Virgil then makes it clear that he believes Everett over Allie.
They wait a while, expecting to be attacked, but then Everett takes Bragg's horse and gives it to the Indians, making peace with them and they head on their way. They come to a small town where the two brothers and Virgil decide to have their showdown. As Virgil and Everett get dolled up for their shootoff, Everett makes a note that Allie's not a loose woman, she just wants to be 'the woman' of the stallion of the herd. The problem is, the stallion changes from time to time. Virgil still makes it clear that even with Allie being how she is, he cares for her and wants her. Allie comes in and watches them for a while, obviously scared. When the men tell her that they're not scared because it's part of the job, she replies that she's always scared that she'll lose everything and have nothing.
As they walk over to the shootout, Virgil and Everett get outgunned by the Marshall of that town and Bragg along with the two brothers, making it a four on two. Virgil takes down a brother and a the Marshall while Everett kills the other brother, but misses Bragg who runs away on a horse. Both Everett and Virgil are wounded, but not seriously. Allie runs to Virgil's body and is obviously distressed.
An unknown amount of time passes, the house is built, Virgil's knee was blown out, so he wears a brace now and they can even laugh a little at everything that happened (including Allie's indiscretions.) However, the town fathers come in and show them that Bragg was pardoned by the President of the Unites States (a man that Bragg claimed to have known, but everyone thought it was just a story.) Later, Bragg comes to down as a gentleman in a fine suit and takes over the main hotel. He tries to make peace with Virgil, but the man will have none of it and Bragg says that now that the town fathers are in his pocket, Virgil's days as the Marshall will be numbered.
Virgil and Everett have a talk, with Everett saying that there isn't really work in Appaloosa for a guy like him. Virgil refuses to leave because Allie is there and is okay with Everett moving on if he has to. Everett has watched Allie go upstairs to a private room with Bragg, obviously she had sensed the power change. She doesn't look happy about it, but she does it.
The next day Everett gives a necklace to the hispanic girl and tells her the name of the one man who he had killed without being a lawman, sounding disappointed at himself about it. He says he's leaving. He takes his horses and rides to the hotel, going into the bar and laying down his badge and a gun to the barman, saying that it's for Bragg. Everett then goes over to Bragg and challenges him, walking outside to wait for him. Bragg gets the gun and storms out of the hotel.
Meanwhile, Everett's woman and Virgil have both come to see what is happening. Virgil tries to stop Everett, but Everett asks him to step aside, noting that he's never asked Virgil for anything. The shootout happens in a second and Bragg falls, Everett doesn't a scratch on him and he mounts his horse and rides out of Appaloosa. It ends with a narration from Everett saying that he gave Allie and Virgil more time to work things out and he's on the road to discovering more about himself again.
You can send in your spoiler to other movies by going here.