A struggle exists for Sweetwater, a piece of land in the desert outside Flagstone which contains the region's only other water source. The land was bought by Brett McBain (Frank Wolff), who foresaw that the railroad would have to pass through that area to provide water for the steam locomotives. When crippled railroad tycoon Morton (Gabriele Ferzetti) learns of this, he sends his hired gun Frank (Henry Fonda) to intimidate McBain to move off the land, but Frank instead kills McBain and his three children, planting evidence to frame the bandit Cheyenne (Jason Robards). Meanwhile, former prostitute Jill (Claudia Cardinale) arrives at Flagstone from New Orleans, revealing that she is McBain's new wife and therefore owner of the land.
The film opens with a mysterious harmonica-playing gunman (Charles Bronson), whom Cheyenne later dubs "Harmonica", shooting three men sent by Frank to kill him. In a roadhouse on the way to Sweetwater, where he also encounters Mrs. McBain, Harmonica informs Cheyenne that the three gunfighters appeared to be posing as Cheyenne's men. Cheyenne arrives at Sweetwater soon after and both men seem attracted to Mrs. McBain. Harmonica explains that, according to the contract of sale, she will lose Sweetwater unless the station is built by the time the track's construction crews reach that point, so Cheyenne puts his men to work building it.
Frank turns against Morton, who wants to make a deal with Mrs. McBain, and immobilizes him under guard on his private train out in the desert. Instead Frank rapes Mrs. McBain, forcing her to go along with it so he won’t kill her, and she is then forced to sell her property in an auction where Frank's men intimidate the other bidders. Harmonica disrupts Frank's plan to keep the price down when he arrives, holding Cheyenne at gunpoint, and makes a much higher bid with the reward money for the wanted Cheyenne. But as Cheyenne is placed on a train bound for the Yuma prison, two members of his gang purchase one-way tickets for the train, intending to help him escape.
Morton now pays Frank's men to turn against him. However, Harmonica helps Frank kill them by directing his attention to their whereabouts from the room where Mrs. McBain is taking a bath – to her outrage. On Frank's return to Morton's train he finds that Morton and his remaining men have been killed in a battle with Cheyenne's gang. Frank then goes to Sweetwater to confront Harmonica. On two occasions, Frank has asked him who he is, but both times Harmonica only answered with names of men "who were alive before they knew you". This time, Harmonica says he will reveal who he is "only at the point of dying".
As the two prepare for a gun duel, Harmonica's motive is revealed in a flashback. A younger Frank forces a boy to support his older brother on his shoulders, while his brother's neck is in a noose strung from an arch. As the boy struggles to hold his brother's weight, Frank stuffs a harmonica into the panting boy's mouth. The older brother curses Frank, and the boy (who will grow up to be Harmonica) collapses to the ground. Back in the present, Harmonica draws first and stuffs his instrument into the dying Frank's mouth as a reminder.
At the house again, Harmonica and Cheyenne say goodbye to Mrs. McBain, who is supervising construction of the railway station as the track-laying crews reach Sweetwater. As the two men ride off, Cheyenne falls, admitting that he was mortally wounded by Morton during the fight with Frank's gang. While Harmonica rides away with Cheyenne's dead body, the work train arrives and Mrs. McBain carries water to the rail workers.
