Part I: Leaving

Former Texas Ranger and comrade of Gus and Call's, Jake Spoon, shows up after an absence of more than a decade. He reveals that he is a fugitive after having accidentally shot the dentist and mayor of Fort Smith, Arkansas, in a bar-room gunfight. The dentist/mayor's brother happens to be the sheriff, July Johnson.

Reunited with Gus and Call, Jake's glowing description of Montana inspires Call to gather a herd of cattle and drive them there, attracted by the notion of settling pristine country. Gus is less enthusiastic, pointing out that they are getting old and that they are Rangers and traders, not cowboys. But he changes his mind when he realizes Lonesome Dove has little left to offer him by way of excitement, now that much of the land has been "civilized".

At the continued insistence of the dentist's widow, Sheriff Johnson sets off in pursuit of Spoon, accompanied by his young stepson Joe who travels at the request of Joe's mother and Sheriff Johnson's wife Elmira. Once her son and husband have left for Texas, Elmira leaves Fort Smith for Ogallala, Nebraska, to meet up with her first husband and Joe's father, Dee Boot. Sailing up the Arkansas River on a whiskey boat, she falls in with a pair of buffalo hunters.

Meanwhile, the men of Lonesome Dove make preparations for their adventure north, including stealing 2,500 horses and cattle from across the Rio Grande in Mexico, befriending two lost Irish immigrants, Allan and Sean O'Brien, and being joined by nearly all of the male citizens of the town. Before leaving, Gus returns to fetch his livery sign and say farewell to his pigs, who end up following him anyway.

Back in Fort Smith, Peach (widowed from Jake's shooting) insists that Roscoe Brown, July's timid deputy, has to find July not only to inform him that his wife's run off, but also that she is pregnant.

Jake decides not to travel with the herd, mainly because he promises to take the town's only prostitute, Lorena "Lorie" Wood, to San Francisco via Denver. Some time later the group survives a huge dust storm, but Sean, one of the Irishmen, is attacked by water moccasins while crossing the Nueces River.

Part II: On the Trail

The young Irishman soon succumbs to his numerous snakebites, dies, and is buried. While travelling through a forest in east Texas, Roscoe encounters Janey, a young girl fleeing from an old abusive "owner". As they travel together they are robbed, when luckily Sheriff Johnson happens to catch up with them. Meanwhile, Johnson's wife Elmira arrives by boat at Bent's Fort, Colorado, and sets off overland across the plains with two hunters interested in her following.

Meanwhile, the camp's cook refuses to cross the river after Sean O'Brien's mishap, so Gus and Call head into San Antonio in search of a new cook. They soon find Po Campo, who gets the job after impressing Gus and Call not only with his cooking, but with his attitude. On the way back, Gus catches up with Lorie, whom Jake has abandoned in order to go gambling in Austin. Before he returns, Gus and Lorie encounter Blue Duck, a notorious Mexican/Indian bandit from Gus and Call's Ranger days. After Gus sends Newt over to Lorie's camp to guard her, Blue Duck knocks Newt unconscious, kidnaps Lorie, and attempts to sell/barter her to a gang of Comanchero bandits camped on the Llano Estacado.

Knowing that Gus is in pursuit, Blue Duck asks the Comancheros to kill Gus when he arrives, with Lorie being their reward. Gus and the bandits engage in a brief gun battle that quickly turns into a stalemate. Gus, having killed his horse for cover on the flat plains, is pinned down by the bandits' gunfire until nightfall, when Sheriff Johnson's party arrives and scares them off. Johnson, despite Gus's protests, joins Gus in the rescue of Lorie. The pair then ride to a hilltop above the Comancheros' camp. After a brief one-sided gunfight, in which Gus kills all of Blue Duck's gang, Lorie is rescued. While Gus and Johnson are away, Blue Duck uses his knife to kill deputy Roscoe, Janey, and Joe. He then steals their horses and escapes. The tearful Sheriff, with Gus's help, buries them all. Gus and Lorie ride north to rejoin Call and the herd. After being severely traumatized by her capture, Lorie now regards Gus as her primary protector. Meanwhile, in a saloon in Fort Worth, oblivious of Lorie's ordeal, Jake Spoon falls in with a gang that is headed north to rob banks in Kansas.

Part III: The Plains

As they ride through the bush, Spoon and the robbers come across a group of horse wranglers. They shoot most of the wranglers and steal the horses. They then travel to a sodbuster's farm, two of whom the leader kills, hangs, and burns for no apparent reason. Although Spoon disagrees, the gang leader bullies and threatens Spoon into submission. When one of the dying wranglers is rescued by the cowboys, Call leads a posse to search for the thieves. Gus and Call quickly capture the robbers and prepare to hang them. With his last words, Jake Spoon admits that it is better to be hanged by his friends than by strangers. Jake, with his head in the noose, then spurs his own horse which causes it to run from underneath him; effectively hanging himself, much to the shock and dismay of his former friends.

By chance, Elmira and the buffalo hunters arrive at the home of Gus' old sweetheart, Clara Allen, near the Platte River in Nebraska. Clara's husband is an invalid, having been kicked in the head by a horse. Elmira gives birth to a son, but abandons the child with Clara and goes to Ogallala in search of Dee Boot. She finds Dee in jail, where he is shortly hanged for a murder. Two weeks later, Sheriff Johnson also arrives at Clara's house and sees his abandoned son. Later in Ogallala, Sheriff Johnson sees Elmira, who is still recovering from childbirth. That night, Elmira secretly departs east for St. Louis with the two buffalo hunters, but all three and their horses are soon killed by the Sioux. Sheriff Johnson returns to Clara's house and is offered a job. Clara, having lost her own three sons to pneumonia, is quite fond of Johnson's newborn son, and names him Martin.

Gus and Call's cattle drive also arrives at Ogallala, where they relax and enjoy the town. Some U.S. cavalry soldiers attempt to commandeer the group's horses, and things intensify when their scout both brutally beats top cowhand Dishwater "Dish" Boggett and viciously whips Newt when they resist, prompting an enraged Call to savagely beat the scout and nearly kill him before Gus restrains him with a lasso. In the aftermath, Gus tells Newt that Call is his father. Clara, although happy to see Gus, and with her husband gravely ill, makes it clear that she will not marry Gus. Instead, she invites Gus to settle and ranch on a piece of nearby property. Further, she invites Lorie to remain with her and her daughters. Before he departs, Gus promises he will return one day.

Continuing their journey, Gus and Call lead their cattle drive north through the badlands of Wyoming Territory, nearly exhausting their water supply, and into Montana Territory. Impoverished Indians soon steal a dozen of their horses for food. Gus, Call, and Deets ride after the horse thieves to retrieve the horses. Call frightens the Indians away with a gunshot. Deets takes pity on a blind Indian child left behind, and goes to assist him. Another Indian mistakes his intentions and impales Deets with a spear. Mortally wounded, he dies in Gus and Call's arms a few moments later.

Part IV: Return

Deets is buried, then the party continues on across the Powder River. Meanwhile, in Nebraska, Clara's husband finally dies and is buried as well.

Leaving the main group to scout ahead with Pea Eye Parker, Gus decides to pursue some buffalo. He and Parker end up being chased by mounted Indians, and Gus is badly wounded by two arrows in his right leg. While trying to get back to the herd for help, an exhausted Pea Eye is guided by the ghost of Deets, whereas Gus is found by a stranger and taken 40 miles away to Miles City, Montana.

There a doctor amputates Gus's right leg. He tells Gus that his left leg is septic and that he will die unless it also is amputated, but Gus refuses to let him remove it. Gus tells Call (who has come in search of him) to give his money to Lorie, to bury him in Texas, and to admit that he, Call, is Newt's father. After some brief reminiscing with Call at Gus's bedside, Gus dies. Call arranges to store Gus's body in the town over the winter. He then leads the cattle drive to a wilderness lake where the party raises a cabin and a corral.

The following spring, Call honors Gus's wish to be returned to Texas. Just before departing, Call gives Newt a pocket-watch that belonged to his own father and states that Newt will run the ranch in his absence. The moment is filled with anticipation, but Call is incapable of actually calling Newt his son out loud.

Call soon returns to Ogallala. Sheriff Johnson, Clara, Lorie, and the ranch hand Dish live happily together. Dish is enamored with Lorie, but she does not return his affections. When Call brings Gus's body, Lorie stays and mourns by the coffin all night long. Clara asks Call to bury Gus at her home, but Call declines. Clara then berates Call for the bad effect he and Gus had on each other, blaming their adventures as the reason neither of them could find happiness.

After a long journey, Call arrives at Santa Rosa, New Mexico Territory, where Blue Duck has finally been captured. Call visits Blue Duck in his jail cell, where Blue Duck mocks Call's failure to capture him. While being led to the gallows, Blue Duck grabs deputy Robert Hofer and throws himself out a window, choosing a murder-suicide rather than allow himself to be hanged.

Despite blizzards, a broken wagon, and the loss of the coffin, Call finally succeeds in burying Gus after a journey of some 3000 miles. Call weeps for his friend after burying him, the first display of emotion he has allowed himself since Deets's death. After the burial, Call tours Lonesome Dove, reunites with his former cook Bolivar, and discovers that the saloon owner who once employed Lorie was so heartbroken by her departure that he burned the saloon down around himself.

As Call walks out of town, a reporter recognizes him and tries to interview him about his remarkable feats. Call ignores the reporter's questions—aside from ironically agreeing with him that he was a man of vision—and walks away.