Set in west Texas about 125 miles from the Mexican border near Del Rio and Langtry, All the Pretty Horses is a story of loss and adventure. John Grady Cole, the main character, is just 16 years old and attending his grandfather's funeral when the novel opens. His mother and father are finally divorcing after years of separation, and his mother is determined to sell the ranch owned by her father. So John Grady sets off on his horse, Redbo, accompanied by his best friend Lacey Rawlins, on his horse, Junior. They ride south across Texas, and, just north of the border, an even younger runaway boy follows them on a big bay horse. Rawlins, the realist, thinks Blevins, who has named himself after a radio preacher, will be nothing but trouble; John Grady, the idealist, is more sympathetic. Sticking together, the three boys ride their horses naked across the Rio Grande River, after securing their belongings in their tied-up pants.
In a lightning thunderstorm, Blevins loses everything except one boot, but a few days later, when they see his horse in a small town, Encantada, the three of them dare to reclaim it, but, of course, they are followed. Blevins separates from John Grady and Rawlins, who finally arrive at a beautiful hacienda that they have heard about on their journey. They find work as cowboys and wranglers, breaking sixteen wild mustangs in four days, to earn their reputations. Soon, because John Grady has proved his abilities with horses, he is promoted to breeder for Senor Rocha, the hacienda owner. A love story begins when the owner's daughter, Alejandra, a year older than John Grady, seduces him. Rawlins tries to warn his friend of the danger he is getting into by entering a relationship with the owner's daughter. The two boys are taken away in handcuffs at the end of Chapter II, when they are caught by the men who saw them take Blevins' horse back and accused of stealing.
Rawlins is very angry with John Grady, who defends himself by saying that some things (meaning passionate love affairs) aren't reasonable. After several days of hard riding, John Grady and Rawlins are put in a small jail cell in an adobe building and find Blevins there with broken feet. A fourth dweller in the cell, an old man, tells the boys that Blevins has killed three men, but Blevins says only one of the men died. After earning money on a farm for two months, Blevins went back to Encantada to retrieve his pistol. Having his horse was not enough for Blevins, and his return to the town where he retrieved his horse has now jeopardized three lives (his own, John Grady's, and Rawlins'). During a transfer south to Saltillo prison, Blevins is shot and killed in the woods. John Grady and Rawlins, after much fighting in the Saltillo prison yard, are both severely wounded. Finally, John Grady is given an envelope of money by the commandant, and they are released. They figure out that Duena Alfonsa, the great aunt of Alejandra, the young girl John Grady loves, has bought their freedom.
Rawlins decides to go home to Texas by way of Nuevo Larado, but John Grady wants to see Alejandra and also try to get their horses back. Rawlins is afraid for John Grady, who reassures him that he is not Blevins. John Grady makes it to La Purisima where the great aunt tells John Grady that Alejandra has promised never to see him again in turn for her great-aunt sending the money to release him from prison. The great-aunt, Duena Alfonsa, also tells John Grady how he has disappointed Senor Rocha by lying and denying any knowledge of Blevins. John Grady claims he wasn't allowed to tell his side of the story, but she says that does not matter. She gives him a horse and he rides to Torreon where he calls Alejandra in Mexico City. She agrees to meet him in Zacatecas, and they both take trains to meet there. Despite their love and his entreaties, she refuses to marry him. He gets drunk but makes his way back to Torreon and the grullo horse, the wild one he first broke with Rawlins a few months before.
At a crossroads while riding north, John Grady turns around and goes to the town where he was first jailed and, by taking the captain hostage, he retrieves his horse (Redbo), Rawlins' horse (Junior), and Blevins' big bay. He has to let the wonderful grullo go, because it is not strong enough for the long trip. But he manages to cross into Texas, again near Langtry, the area of Judge Roy Bean, where he travels for several months, trying to find the rightful owner of the bay. A judge helps him when some degenerates try to claim the horse. The judge listens to John Grady's story and assures him that the man he killed in prison and the captain who jailed them in the small town are not good people. The judge tries to urge John Grady to go easier on himself.
In Del Rio, Texas, John Grady visits the real Jimmy Blevins, who has never heard of anyone fitting the boy's description and has never seen the horse. After feeding John Grady a big meal and telling him about the radio preaching business, the reverend goes off to write a sermon. John Grady rides back to San Angelo and goes to Rawlins' family place and whistles for his friend, who is delighted to see John Grady and his horse, Junior.
After attending, on the sidelines, the funeral of the old woman, Abuela, who had done most of the work raising him, John Grady rides west, a lonely figure on one horse, leading his second mount.