The Black Company's current employer, the Syndic of Beryl, is losing control of his decadent city to rival factions. A dangerous monster known as a forvalaka runs amok through the city, killing numerous citizens and contributing to the city's growing instability; the Syndic requests that the Black Company track and kill the beast. The creature is virtually indestructible, and it kills several of the Black Company's men, including Tom-Tom, one of the Company's wizards. When the Taken named Soulcatcher offers the Company new employment in the service of the Lady, its Captain readily accepts, though he is forced to arrange the murder of the Syndic to break the contract.
On the march north to the Lady's empire, the Company acquires two new members. Raven is an uncommonly deadly and (usually) remorseless recruit, even by Company standards. Uncharacteristically, he rescues Darling, a nine-year-old mute girl being abused by soldiers affiliated with the Limper, another of the Taken. The Limper and Soulcatcher are deadly rivals; since the Company was recruited by Soulcatcher, that makes the Limper an enemy to beware.
After weeks of trying to link up with the Limper's forces, the Company (at Soulcatcher's suggestion) takes an important rebel fortress, embarrassing both the Limper and Raker, a leading member of the Circle of Eighteen. The Limper sends his top aide, Colonel Zouad, to stir up trouble for the Company, but Elmo, the Company's Sergeant, leaks his whereabouts to the rebels, allowing them to abduct him for information. Zouad manages to contact the Limper, but Soulcatcher has other plans. When the Limper cracks open the underground room where his minion is being held, Shapeshifter, Soulcatcher's Taken ally, is waiting disguised as a rebel and unexpectedly stuns him with magic. Shifter then rolls the incapacitated Limper into the cellar and causes it to collapse in on itself. Another victory for the Company, another humiliation for the Limper. While the Limper is not killed, this slows him down for a time.
While the Limper is absent from his post, Raker's troops attack and part of the front collapses. The Company is caught up in the general retreat but shows itself to be the Lady's most effective unit in the ensuing battles. The Captain is given authority normally reserved for the Taken.
Raker is targeted next. The Company's wizards, with Soulcatcher's backing, display a fortune in gold, silver and jewels (protected by magic) in a nearby, neutral city – a bounty for his head. Raker has no choice but to try to steal it before half the world tries to collect. Isolated when he ignores the Circle's order to withdraw, he is eventually killed by Raven and Croaker, but not before his disobedience saps the morale of the rebels in the region.
Retreating once more, the Company stumbles upon and captures a rebel training camp. Papers are found that belong to Whisper, the strongest member of the Circle and a military genius as well. One details a future meeting with the Limper, who is ready to defect as a result of his string of disasters. Soulcatcher, Raven and Croaker ambush them. All the while Croaker has a nagging suspicion that someone is watching them; he later learns it is Silent, a Company wizard. They are captured alive and presented to the Lady. Limper is sentenced to centuries of torture by the Lady.
After the Lady uses magic she learned from the Dominator to gain Whisper's unswerving loyalty, the new Taken is sent to the eastern front. The war becomes a race: the rebel armies in the north, under the overall command of Circle wizard Harden, drive the Imperial forces back towards the Tower at Charm, the headquarters of the Lady, while Whisper runs amok in the east, laying waste to the heartland of the rebellion.
Harden is killed, but takes the Taken The Hanged Man with him. The Circle suffers more casualties, but massive rebel forces besiege the Tower. A daring sortie by the Company captures the wizards Feather and Journey, weakening the Circle further; they are transported to the Tower to share Whisper's fate.
The battle for the Tower begins. The Circle's forces number a quarter of a million while the Lady can muster a mere 21,000. Yet so dangerous are the Lady and the Taken that the Circle delays, hoping to find the prophesied reincarnation of the White Rose to lead them. A great comet hangs in the sky for most of the battle. A prophecy says the Lady and the Dominator will be defeated under a comet's fiery tail. Finally, the rebels are forced to attack without the White Rose before the empire's victorious eastern armies can arrive. All of the Taken gather to bolster the defenses, killing the remaining members of the Circle, when they are not busy assassinating each other. Except for Soulcatcher, all of the original Taken are slain, some by the rebels, but more from internal backstabbing. During the fighting, Croaker observes that Darling seems to be immune to magic. Finally, the rebels are utterly devastated.
Then, with her plot to take over the empire discovered, Soulcatcher flees, but the Lady, with Croaker along as a witness, tracks her down. The physician shoots her with magical arrows supplied by the Lady and then beheads her. Croaker then learns that Soulcatcher is the Lady's own sister. Afterwards, he speculates that this was what the Lady had intended all along: not only to crush the revolt, but also to rid herself of all the treacherous Taken.
During the confusion, Raven deserts because he knows something he does not want the Lady to learn, taking Darling with him. Raven, Croaker and Silent all believe that Darling is the reincarnated White Rose.
