Paladin of Souls is a sequel to The Curse of Chalion and is set some three years after the events of that novel. It follows Ista, mother of the girl who became Royina (Queen) in that book and a minor character in it. Recovering from the extreme guilt and grief that had marked her as mad while the Golden General's curse on her family persisted, she finds herself bored to distraction and restless. To get away from her home town, Valenda, and its ugly memories she sets out on a religious pilgrimage with the dy Gura brothers (also minor characters from the earlier story) for protection; Liss, a feisty and clever courier girl; and dy Cabon, a plump priest of the Bastard (one of the five gods) as her 'spiritual guide'. The Bastard, god of disasters and of things out of season, becomes a larger presence in this novel than was The Lady of Spring in The Curse of Chalion; by its end, Ista herself has become a saint in his service. (The Father of Winter, another of the five gods, also makes a brief appearance.)
The pilgrimage party is overrun and captured by a troop of Roknari raiders from the adjacent principality of Jokona, then set free by a patrol from nearby Castle Porifors. Leading the rescuers is Arhys, lord of the castle and a very effective warrior indeed—considering that he scarcely eats or drinks, or sleeps except for brief afternoon naps. Though she comes to be immensely attracted to him, she realizes in horror that he is the son of a man she had helped murder. Another obstacle is Arhys's very young and very beautiful wife, Cattilara. Once in the castle Ista discovers another odd man: Lord Illvin, Arhys's half-brother. He is unconscious except for afternoon wakings that match Arhys' naps. She has seen him before, though, in a baffling dream that at last makes some sense. As this mystery begins to come clear, Castle Porifors is besieged by a new force of Roknari from Jokona that includes its Prince, Sordso, and his mother, Princess Joen. The latter is an elderly, minor daughter of the Golden General and has accumulated a whole troop of demon-ridden magicians, including her son, all of them controlled by one major magician: herself.
As Castle Porifors and its defenders crumble under magical siege, Lord Arhys and a picked troop make a night raid that jolts the Jokonans but does not dislodge them. Only when Ista allows herself to walk as a hostage into the Princess' lair is the siege ended. The remaining magicians' demons are sent back to the Bastard's care, and the remaining loose ends of the story are resolved, with Ista's acceptance of the Bastard's offer of skills and a job that give use and meaning to the rest of her life. Lord Illvin comes with the job as a bonus.