Senator Ranse Stoddard and his wife Hallie arrive in Shinbone, a frontier town in an unnamed western state, to attend the funeral of Tom Doniphon. As they pay their respects, reporters ask Stoddard why a United States Senator would make the long journey from Washington to attend the funeral of a local rancher.
The story flashes back 25 years; Stoddard is a young, idealistic attorney. His stagecoach is robbed by Liberty Valance and his gang. When Stoddard tries to take Valance to task, Stoddard is brutally whipped and left for dead. Doniphon finds him and takes Stoddard into the town of Shinbone, where Hallie and other townspeople tend to his injuries and explain that Valance victimizes Shinbone residents with impunity. Marshal Link Appleyard lacks the courage and gunfighting skills to challenge him. Doniphon (who is courting Hallie) is the only man willing to stand up to Valance.
Stoddard opens a law practice in Shinbone, inviting retribution from Valance, who cannot abide challenges to his "authority". Force, Doniphon explains, is the only thing Valance understands, but Stoddard advocates justice under the law, not brute force.
Stoddard earns the town's respect by refusing to knuckle under to Valance, and by founding a school to teach reading and writing to illiterate townspeople, including Hallie. Hallie discovers Stoddard is practicing with a gun and fretfully tells Doniphon, which raises his suspicions about Hallie and Stoddard's relationship.
When Doniphon notices that Stoddard is trying to teach himself to use a revolver, he offers the inexperienced Stoddard a lesson in marksmanship. During target practice, Doniphon effortlessly shoots three paint cans; the final one showers Stoddard with white paint, ruining his suit. Tom explains that this is the sort of trickery that he can expect from Valance. Infuriated, Stoddard punches Doniphon in the jaw and leaves.
Shinbone's residents meet to elect two delegates for a statehood convention at the territorial capital. Doniphon nominates Stoddard, because he "knows the law, and throws a mean punch."
Stoddard explains that statehood will improve infrastructure, safety, and education. The cattle barons oppose statehood and hire Valance to sabotage the effort, but Stoddard defies Valance again. The townspeople elect Stoddard and Dutton Peabody, publisher of the local newspaper.
Valance challenges Stoddard to a gunfight. Doniphon advises Stoddard to leave town, but Stoddard believes in the rule of law and is willing to risk his life for his principles.
That evening, Valance and his gang catch the drunken Peabody, beat him nearly to death, and ransack his office. Stoddard goes into the street to face Valance. Valance toys with Stoddard, shooting his arm and laughing at him. The next bullet, he says, will be "right between the eyes", but Stoddard fires first, and to everyone's shock, Valance falls dead.
Doniphon watches Hallie care for Stoddard's wounds, then heads for the saloon. At his homestead, in a drunken rage, Doniphon sets fire to the addition that he has just finished in anticipation of asking Hallie to marry him. His African American ranch hand, Pompey, rescues Doniphon, but the house is destroyed.
At the statehood convention, Peabody nominates Stoddard as the territory's delegate to Washington, DC, but Stoddard's "unstatesmanlike" conduct is challenged by a rival candidate. Stoddard decides that he cannot be entrusted with public service after killing a man in a gunfight.
Doniphon takes Stoddard aside, and in a flashback within a flashback, confides that he, Doniphon, actually killed Valance from an alley across the street, firing at the same time as Stoddard. Reinspired, Stoddard returns to the convention, accepts the nomination, and is elected to the Washington delegation.
The original flashback ends, and Stoddard fills in the intervening years. He married Hallie, and then, on the strength of his reputation as "the man who shot Liberty Valance", became the new state's first governor. He then served as a U.S. Senator and United States Ambassador to the United Kingdom before returning to the Senate, and now there is talk of a vice presidential nomination.
The reporter realizes that Stoddard's entire reputation is based on a myth, but after reflection throws his interview notes into the fire. "This is the West, sir," he explains. "When the legend becomes fact, print the legend."
On the train back to Washington, Stoddard informs Hallie, to her delight, that he wants to retire from politics and practice law in Shinbone. When he tells the train conductor that he will write to railroad officials, thanking them for their many courtesies, the conductor replies, "Nothing's too good for the man who shot Liberty Valance!"
