America, 1911. The age of gunslingers is coming to an end as the country races towards modernization, but the Wild West is ever untamed and chaotic.
Enter John Marston, a former outlaw who ran with a gang lead by the notorious Dutch van der Linde, arriving in the state of New Austin in search of one of his former brothers-in-arms: Bill Williamson, a viscous bandit of ill repute who was holed up in an old fort. When John goes to confront Williamson, however, he ends up being shot and left for dead.
Thankfully, a female rancher, Bonnie MacFarlane, happens upon him and takes her back to her family's ranch to recover. In gratitude, John offers to help out around the ranch, learning how to break horses and herd cattle. Becoming fast friends with the fiesty Bonnie, John reveals the reason he came looking for Williamson: he is acting under orders from the United States government to take out the last members of Dutch's gang, forced into their service under threat of grave harm to his wife and son.
This quest to end Williamson leads to John doing odd jobs and favors for various people across New Austin in addition to assisting Bonnie. In his travels, John meets and befriends Leigh Johnson, a beleaguered US Marshall; Nigel West Dickens, a notorious snake oil salesman; Seth Briars, a mentally unhinged grave robber; and "Irish", an immigrant arms dealer and infamous drunkard. In time, the favors that John does for these people pay back when they offer their services in helping to raid Williamson's hideout; Johnson and his deputies join John while Seth provides a distraction that lets West Dickens sneak him inside from within an armor-plated carriage outfitted with a Gatling gun provided by Irish.
In the end, however, Williamson manages to escape to Mexico in the fighting with the aid of another old member of Dutch's gang, Javier Escuella. John pursues his nemesis south of the border, entering into a state embroiled in a civil war between the Mexican government, with a force led by Colonel Augustin Allende, and a rebel army led by Abraham Reyes, a former aristocrat who started a peasant revolt. At first, John works with Allende and his captain, Vincente de Santa, in exchange for help in finding Escuella and Williamson, even though doing so leaves a bad taste in his mouth: Allende's methods of dealing with rebels are very heavy-handed, leading to many innocents dying and women being abducted for his own sick pleasures, with de Santa all too happy to aid him.
Eventually, de Santa betrays Marston and prepares to have him killed, only to find himself ambushed by Reyes and his rebels. After capturing and killing de Santa, John enlists the rebels' aid in helping him finally capture Escuella, who reveals that Allende had been giving Williamson sanctuary. Afterwards, John and the rebels lay siege to Allende's fortress, with Allende and Williamson attempting to make an escape. Unfortunately for them, John and Reyes catch up to them and put them out of their misery.
With Williamson finally dead, John leaves Mexico returns to America, making for the office of the Bureau of Investigation to discuss the release of his family with the agent who forced him into hunting down Williamson, Edgar Ross. To his vexation, Ross refuses to release John's family until he does one more job for them; hunting down and killing his old leader, Dutch van der Linde. According to an informant, a Native American named Nastas, Dutch had been building a new gang, one consisting of disenfranchised Native Americans who resented the government for the injustices they had suffered. With the aid of the US Army, John and Ross lay siege to Dutch's new gang, and John pursues Dutch until he has him backed into a corner on a cliff. Dutch claims to be fighting for something greater than himself, before finally conceding that he just can't fight nature and throws himself off of the cliff and to his own demise.
With Dutch dead and his gang finally dismantled for good and all, Ross finally honors his end of the deal and tells John that his family had been returned to their ranch. John returns home and finally reunites with his wife, Abigail, and his son, Jack. At long last, it seems as though John can finally leave his past behind and live an honest life as a farmer and rancher, reconnecting with his estranged son and bonding once more with his beloved wife.
Unfortunately, the past has a way of catching up to John in the worst way possible; the US Army suddenly descends on John's farm, intent on killing him and his family. After fending on several soldiers, John has his wife and son make their escape.
...but there would be no escape for John. After Jack and Abigail leave, John stays behind in the farm and sees himself confronted by scores of soldiers, led by Edgar Ross. Resigning himself to his fate, John steps out and challenges the army. In the end, however, John is hopelessly outnumbered and outgunned. He is shot several times and, in spite of his defiance that keeps him standing for several moments, succumbs to his wounds and dies. After Edgar and the army leave, Jack and Abigail turn back to the farm, only to find John's body...
That day, Jack and Abigail lay John to rest with a homemade grave on his farm. His epitaph reads: "Blessed are the peacemakers."
Three years later, Abigail joins John in the hereafter when she passes away. Jack, now an adult, visits his parents graves one rainy day before setting off for the west. Once an idealistic young man who aspired to become a writer, now he is a disillusioned drifter, travelling through the west as an outlaw; the kind of life his father wished to protect him from. Jack's travels eventually bring him face to face with Edgar Ross, now retired from the Bureau and renowned as a hero who helped bring criminals to justice. Few know Ross as the kind of man Jack knows him for, however; a corrupt man who manipulated his father, a man who wanted to lead an honest life, into doing his dirty work, and who had that man murdered when he was no longer of any use.
For this, Jack can answer in the only way he now knows how: by putting Ross down like the monster that he was.