Part 1

A young psychopathic Mexican bandit named Joey Garza has murdered numerous people, and cost railroad tycoon Colonel Terry significant business and money through his deadly train robberies. Captain Woodrow F. Call is a grizzled veteran of the west, a man in stark contrast to the inexperienced urban Ned Brookshire, who has been sent to Clarendon, Texas, from New York by Terry to contract Call's services in apprehending the bandit. They form an unlikely pair as they search for Garza, and soon they learn in Laredo, Texas, that he is not the only outlaw preying on the railroad.

Pea Eye Parker, formerly of the Hat Creek outfit, now owns a farm in the Texas Panhandle. He is married to Lorena Wood, the former whore and lover of Gus McCrae, and now a school teacher. Pea Eye is devoted to her and their five children, and she has learned to reciprocate and become almost equally as attached to him. He is, however, increasingly pressured by his wife to settle down, so he initially declines to accompany Call and Brookshire in the hunt for Garza. His loyalty and devotion to Call finally prevails, though, and he sets out after Call, where he is soon joined by the celebrated Kickapoo tracker, Famous Shoes.

The series also follows the family of 19-year-old Joey Garza. Joey's mother, Maria, is the midwife of Ojinaga, a small Mexican village on the Rio Grande. She has had a string of brief, failed marriages and has three children, of which Joey is the oldest. Joey, in possession of a Swiss sniper rifle, learns that Call is after him and having shot a gringo, hides out in Crow Town, an outlaw village deep in the borderland desert. The law arrives, and in her son's absence, Maria is taken over the river and is brutalized by the deputies there.

Lorena, meanwhile, learns that a former flunky of Blue Duck, Mox Mox, is alive. Known for burning his captives alive, he was thought to have been killed years before. The news, brought by Charles Goodnight, is especially traumatic for her, since she had nearly been burnt by him while she was a captive of Blue Duck. Fearing for the lives of her children, she sends them on the train to Nebraska, to the protection of her friend Clara Allen.

Part 2

Garza continues his killing spree, returning often to his abandoned mine hideout to store his loot. Maria, now rescued from the deputies by Billy Williams, goes to Crow Town to warn her son that Call is getting closer. She still has reason to hate Call, who had her father and brothers hanged for rustling 30 horses. Call, now in Chihuahua City and also accompanied by Laredo Deputy Ted Plunkert, receives news updates by telegram of the ongoing killings and that the other killer is a past nemesis called Mox Mox.

Garza, still hiding out west of the Pecos River in Crow Town, soon meets another notorious denizen—the legendary Texas gunfighter, John Wesley Hardin. After Maria arrives to warn him, she kills the town's "devil pig" and later butchers it after Joey disappears and steals her horse. She then sets off back home, but not after inviting the town's whores to accompany her on the walk back. Mox Mox and his gang soon arrive in Crow Town looking for Garza, seeking him for the payrolls he stole and denied them, and leave after a tense stand-off with Hardin.

Meanwhile, Corporal Pea Eye and Famous Shoes, unaware of the threat of Mox Mox, continue south to find Captain Call. They are thrown into the Presidio jail when the sheriff accuses Famous Shoes of being a horse thief and decides to hang him. Captain Call, arriving in Ojinaga, hears of their plight and crosses the river to free them from jail, near-killing the sheriff after he refuses to allow their release on order of the governor. He then continues in pursuit of Mox Mox. He ambushes the gang alone just as they are about to burn Jasper Fant's children alive, killing all but two - Quick Jimmy, a renegade Cherokee, who escapes unscathed, and Mox Mox himself, who soon dies. Meanwhile, Lorena, in search of Pea Eye, arrives in Laredo, and Garza rides off to Langtry, Texas, where he shoots and hangs Judge Roy Bean.

Part 3

Call accompanies the children back to Fort Stockton, Texas, just as Lorena arrives in town. They then head off together to find the posse, but Garza shoots Call thrice after he rides out to check on three nearby horses. Severely wounded, and unable to make it back to town in time, he asks Lorena to amputate his right leg. This done, they finally end up back in Maria's house in Ojinaga.

On the trail, Deputy Plunkert receives news of his wife's suicide and rides off for Laredo, but is soon killed and stripped by bandits. Call's remaining posse is then ambushed by Garza, who shoots the horses and steals their provisions. Brookshire, despairing of the situation, decides to face Garza, but is shot dead in cold blood. In the morning, Famous Shoes returns and asks Pea Eye for his boots, since Garza feels he will not be followed without them. Pea Eye, however, has him scout where Brookshire's shotgun is, and despite being wounded, manages to spray Garza with buckshot.

Garza then drags himself back to his native village and attempts to kill his younger siblings. Maria tries to stop him, but he stabs her. The butcher then mortally wounds him. Lorena and Bill return with Pea Eye just as Maria dies from her wounds. At her request, Pea Eye and Lorena adopt Maria's two surviving children, and return with them to their farm. Call, crippled and no longer able to pursue bandits, goes to live with them, and becomes increasingly attached to Teresa, Maria's blind daughter, demonstrating for the first time an attachment to anyone besides Gus McCrae.