Thomas Dunson (John Wayne) is a stubborn man who wants nothing more than to start up a successful cattle ranch in Texas. Shortly after he begins his journey to Texas with his trail hand Nadine Groot (Walter Brennan), Dunson learns that his love interest Fen (Coleen Gray), whom he had told to stay behind with the California-bound wagon train with the understanding that he would send for her later, was killed in an Indian attack.
Despite this tragedy, Dunson and Groot press on. That night, Dunson and Groot fend off an attack by Indians, and on the wrist of one, Dunson finds a bracelet he had been left by his late mother, which he had given to Fen as she left. The next day, an orphaned boy named Matthew Garth (played as a boy by Mickey Kuhn and as an adult by Montgomery Clift) wanders into Dunson and Groot's camp, traumatized and babbling incoherently. He is the sole survivor of the wagon train. Dunson adopts him and ties the boy's cow to his wagon, alongside his own bull.
With only the bull and the cow, Dunson, Groot, and Matt enter Texas by crossing the Red River. They finally settle in deep South Texas near the Rio Grande. After Dunson proudly proclaims all the land about them as his own, two Mexican men appear on horseback and inform Dunson that the land already belongs to their boss, a Spanish grandee whose family held the land by patent from the King of Spain. Dunson dismisses this and, thanks to a quicker draw in a showdown, kills one of the men and tells the other to inform the Spanish don that Dunson now owns the land. Dunson names his new spread the Red River D, after his chosen cattle brand for his herd. Fatefully, he promises to add M (for Matt) to the brand, once Matt has earned it.
Fourteen years pass, and Dunson now has a fully operational cattle ranch. With the help of Matt and Groot, his herd now numbers over ten thousand cattle, but he is also broke as a result of widespread poverty in the southern United States. Due to its loss of the American Civil War, the South cannot afford Dunson's beef. Dunson decides to drive his massive herd hundreds of miles north to the railhead at Sedalia, Missouri, where he believes they will fetch a good price. After Dunson hires some extra men to help out with the drive, including professional gunman Cherry Valance (John Ireland), the perilous northward drive starts.
Along the way, they encounter many troubles including a stampede sparked by one of the men, Bunk Kenneally (Ivan Parry), making a clatter while trying to steal sugar from the chuck wagon. This leads to the death of Dan Latimer (Harry Carey Jr). Dunson wants to make an example of him by whipping him, but when Bunk draws his gun in self-defense, Matt shoots Bunk in the arm, knowing that Dunson would have shot to kill. The wounded Bunk is sent to make his way home on his own.
Continuing with the drive, Valance relates around the campfire one evening that the railroad has reached Abilene, Kansas, which is much closer than Sedalia. When Dunson confirms that Valance had not actually seen the railroad, he ignores what he regards as a rumor in favor of continuing on to Missouri. Deeper problems arise when Dunson's tyrannical leadership style begins to affect the men. One of the two chuck wagons was destroyed in the stampede, causing morale to drop as the men live on nothing but beef and roasted grain "coffee." Dunson tells the men he is broke and cannot buy more supplies, even if they turned back to get them. When he announces he intends to lynch two men who tried to desert, Matt rebels and takes control of the herd in order to drive it along the Chisholm Trail to the hoped-for railhead in Abilene, Kansas. Valance and Buster (Noah Beery Jr.) become his right hand men. Face to face, Dunson curses him and promises to kill him when next they meet. The drive turns toward Abilene, leaving the lightly injured Dunson behind with his horse and a few supplies. Matt and his men are well aware that Dunson will try to recruit a posse to pursue them.
On the way to Abilene, Matt and his men repel an Indian attack on a wagon train made up of gamblers and dance hall girls. One of the people they save is Tess Millay (Joanne Dru), who falls in love with Matt. They spend a night together, and he gives her Dunson's mother's bracelet, evidently given to Matt by Dunson in earlier years. Eager to beat Dunson to Abilene, he leaves early in the morning, the same way Dunson had left his lady love with the wagon train 14 years before.
Later, Tess encounters Dunson, who has followed Matt's trail and now sees her wearing his mother's bracelet. Weary and emotional, he tells Tess what he wants most of all is a son. She offers to bear him one if he will abandon his pursuit of Matthew Garth. Dunson sees in her the same anguish that Fen had expressed when he left her, but he resumes the hunt with Tess Millay accompanying him.
When Matt reaches Abilene, he finds the town has been eagerly awaiting the arrival of such a herd to buy and ship it east by rail. Unknowingly, he has completed the first cattle drive along what would become famous as the Chisholm Trail. He accepts an excellent offer for the cattle and also meets Tess again. Shortly thereafter, Dunson arrives in Abilene with his posse. Valance tries to keep the two apart, but Dunson beats him to the draw, badly wounding him while Valance inflicts a flesh wound on Dunson. Dunson and Matt begin a furious fistfight, which Tess interrupts by drawing a gun on both men, shooting wildly and demanding that they realize the love that they share. Dunson and Matt see the error of their ways and make peace. The film ends with Dunson advising Matt to marry Tess, and telling Matt that he will incorporate an M into the Red River D brand as he had promised 14 years before, because he has earned it.
