Once again caught short of mercury for his TARDIS’s fluid links, the Doctor and his companion Catherine Broome must steal some from the Wierdarbi, a fearsome race of cybernetically enhanced insects. The Wierdarbi corner them by the TARDIS, but Cat releases a swarm of prototype robots from the Doctor’s workshop as a distraction. She and the Doctor escape, but in the confusion, the Doctor loses his precious Gladstone bag. Cat thus suggests a shopping expedition, and the TARDIS takes her and the Doctor to a marketplace on the planet Haven.

This is probably the worst place it could have chosen. Haven is a primitive world which should not have been contacted by humanity; however, due to famine in the outer worlds, the rules were stretched, and Haven was contacted by missionaries from the Catholic Church who converted much of the humanoid population. Sixteen months ago, however, a malfunctioning TARDIS materialised on Haven and exploded, and the dimensional breach had devastating effects on the planet and its inhabitants. In the aftermath, the Church has declared all Time Lords to be witches...

A native named Philippo sees the Doctor’s TARDIS materialise just outside the marketplace, and immediately rushes to the Cathedral of Braak, enters a confessional and warns the priest within that the witches have returned. The priest sends Philippo back to the market to keep an eye on the strangers from the Devil-box, while Bishop Agatho, who has wiretapped the confessionals, reports the incident to his superiors.

The Doctor is entertaining the crowd with juggling and magic tricks while Cat shops for a new bag, but when he innocently picks Philippo as a “volunteer” for a trick, the terrified Philippo accuses him of witchcraft. Cat is forced to hide as the crowd turns into a mob and descends on the Doctor, and though he tries to reason with him, they become even angrier when he refers to his TARDIS by name. The Doctor realises that these people have been visited by Time Lords before, obviously with devastating results, but this realisation comes too late, as the mob prepares to burn him at the stake.

Cat prepares to rush to the rescue, but before she can do so, a spaceship in the shape of a gigantic cross descends upon the marketplace. The terrified mob disperses as agents of the Holy Inquisition emerge to arrest the Doctor. Grand Inquisitor Guii del Toro, displeased to see that the Doctor was nearly lynched before he could be interrogated, drags the protesting Philippo aboard the ship for further questioning and orders his guards to take the TARDIS into the cathedral. Aboard the ship, del Toro informs the Doctor of the disaster caused by the Time Lords, and reveals that he has already “interrogated” the survivors on a torture device which resembles a cross between a crucifix and a TARDIS time rotor. He now intends to torture the Doctor, using the machine to force him to regenerate repeatedly and questioning the Doctor’s future incarnations in their post-regenerative confusion.

Cat infiltrates the crowd carrying the TARDIS into the cathedral, and hides in a confessional, where a sympathetic priest named Father Julian convinces her to tell him her story. Cat admits that she travels with a Time Lord, although it now occurs to her that she can’t remember where they first met. Father Julian -- a former Patriarch of the Spinward Colonies, who gave up his exalted position to live as a simple Benedictine -- offers to intervene on the Doctor’s behalf, but fears he will have little influence with the vicious and ambitious del Toro.

del Toro begins to torture the Doctor, but he is interrupted by Cardinal Runciman, Archbishop of the Southern Rimworlds. The Inquisition is transporting Runciman to Rome for an important papal conclave, but he suspects that del Toro has delayed the journey for reasons of his own. Runciman orders del Toro to finish his work immediately, and retreats to the cathedral to pray before his departure. Meanwhile, the Doctor’s spirit leaves his body, apparently drawn out by the torture machine, and in this disembodied state he witnesses Runciman’s murder, as a monk strikes him down before Cat and Father Julian’s eyes. Julian sees the monk’s face and faints dead away, believing he’s seen the Antichrist. Agatho has Cat arrested for the murder, but as the Bishop addresses his congregation, the Doctors’ spirit appears in front of the TARDIS, and the people of Haven panic and flee from the cathedral.

The Doctor manages to reunite his spirit and body, but finds that he and Cat are now to be executed for Runciman’s murder. However, Father Julian recovers and identifies the real killer as a monk with no face. Since Cat is Roman Catholic, as far as she remembers, and the Doctor was made an honorary dean of Westminster Abbey by the Venerable Bede, the Doctor demands to be taken to Rome to have their case heard by the Pope. del Toro agrees to do so, but Father Julian realises that he just wants to charge a Time Lord with murder before the papal conclave. Pope John Paul XIII has been brain-dead for years, and will soon be declared legally soul-dead; the conclave is meeting to elect a new Pope, and del Toro intends to put his name forward.

The Inquisition thus departs from Haven, taking with them Bishop Agatho and Philippo. Philippo, who has never travelled in his life, is wracked with terror and despair at being taken offworld, while Agatho fears for his own safety and worries that del Toro intends to abandon the “Good Shepherd” project. Meanwhile, Cat explores the lower levels of the Inquisition’s mothership, and meets a friendly young priest named Paddy O’Hearne. Cat confesses that she’s been having trouble remembering her past, and finds to her surprise that she and Paddy share several formative childhood experiences in common, though obviously they were born centuries apart.

The Doctor learns from del Toro that the Catholic Church has become divided over the issues raised by contact with alien life forms and civilisations. One particularly violent schism led to Pope Athanasius fleeing Earth and relocating Rome to a mobile space station. The Catholics who remained on Earth elected a new Pope; they refer to the space-station Rome as “Avignon”, and both Popes consider the other to be false. Also, the despotic Magellanic Tsar, Brotak, has named his own Pope, a corrupt and decadent Cetacean who has changed his name from Brrteet’k to Celestine and is supporting Brotak’s warmongering ambitions. Word then reaches the Inquisition that the Pope has been declared legally soul-dead. Pope Urban XII has left Earth to attend the conclave and stake his claim to the papacy of Avignon/Rome, and del Toro fears that Celestine’s forces may also move to legitimise his claims.

Cat questions the Doctor about the gaps in her memory, fearing that the Church may somehow be planting false memories in her head. Her fears seem justified when she meets Paddy again and the priest doesn’t appear to recognise her. Dissatisfied with the Doctor’s vague replies, Cat seeks out Father Julian and confesses that she has doubts about the nature of the soul. She has seen gestalt entities with billions of bodies, and creatures such as the Cybermen who have converted themselves into machines. What does this mean for their souls? If Time Lords are capable of regeneration, does this mean that each of the Doctor’s personalities has an individual soul? Julian can provide no answers, and as he sets off to investigate a disturbance elsewhere in the ship, Cat goes looking for Paddy. Instead, she finds Philippo flagellating himself before the TARDIS in despair while Bishop Agatho reprogrammes an android which resembles Paddy. Agatho reveals that he was ordered to murder Runciman, and that he’s trying to erase the android’s memory so he won’t be called to account for the crime. He tries to strangle Cat so she won’t tell anyone, but at the last moment he lets go of her throat and begins to laugh...

The disturbance which Julian was investigating turns out to be an attack by the Magellanic Tsar’s barbarian hordes; they have attacked the outer planets in support of Celestine’s claim to the papacy, and the Inquisition’s mothership is now in the middle of a war zone. Enemy forces commanded by General Grigg board the ship and release toxic gas in the corridors. The human guards are cut down, but the Doctor reveals that there are other potential fighters on board; he has deduced that many of the priests, such as Paddy, are androids. This is the “Good Shepherd” project, an attempt by del Toro and Agatho to ensure dogmatic unity by using pre-programmed priests to spread the word. Agatho used one of these androids to murder Runciman after removing its flesh mask. del Toro admits that he ordered Agatho to help him keep Runciman from reaching Rome, but claims that Agatho exceeded his authority.

The Doctor reprogrammes the robots to defend the ship and takes del Toro and Julian to the cargo hold to escape in the TARDIS. However, Philippo’s sanity has been pushed to the limit by seeing the corruption of his church elders, and when he is told that he will have to board a TARDIS, he snaps and attacks del Toro. As they struggle, they fall into the machine in which the Doctor was tortured, and their bodies fuse together into a single organism which quickly dies. The Doctor realises that del Toro intended to learn from the Time Lords how to regenerate.