The TARDIS materialises in 12th century Israel, during the time of the Third Crusade. When the Doctor, Ian, Barbara, and Vicki emerge, they find themselves in the middle of a Saracen ambush. In the confusion, Barbara is captured by the Saracens, while the rest of the TARDIS crew stop the attackers from killing William de Tornebu, an associate of King Richard. William des Preaux, another companion of the king, is also captured by Saracens and pretends to be Richard in order to protect him. The Doctor, Ian, and Vicki agree to take the wounded de Tornebu back to Richard's court, but first must steal clothes from the market in order to blend in.
Meanwhile, des Preaux and Barbara are presented to Saladin's brother Saphadin by El Akir, who mistakenly believes them to be King Richard and his sister Lady Joanna. When des Preaux reveals their true identity, El Akir is furious but, before he can act, Saladin emerges from hiding and prevents any violence from occurring. Saladin is intrigued by Barbara, who tells tales of having met Nero, and tells her she can become the new Scheherazade.
The disguised Doctor and company bring the injured de Tornebu to the King's court. They are met by Richard, who witnessed their fight during the ambuscade. The King, however, is in a foul mood, and treats the TARDIS crew very curtly. Ian, anxious to rescue Barbara, asks for the King's help in rescuing her, but the irritated monarch tells Ian that Barbara can remain with Saladin until her death.
De Tornebu and the Doctor are able to convince the King to change his mind by playing up the embarrassment Saladin will feel when it's revealed he has not actually captured the King. Richard is amused, and asks the Doctor to join his court. Ian is knighted "Sir Ian of Jaffa" so that he may serve as a proper emissary, and is sent to Saladin's court to both request the release of des Preaux and Barbara, and to offer the hand of the real Lady Joanna in marriage to Saphadin. When Joanna learns of these plans, she is infuriated, and tells her brother she will not consent.
Ian, on the way to Saladin's court, is attacked by bandits and knocked out. When he claims to have no money, one of the bandits, Ibrahim, ties him down with stakes in the hot sun and daubs him with honey. He tells Ian the ants will loosen his purse strings.
Barbara manages to escape, and is taken in by Haroun ed-Din. He is sympathetic because El Akir killed his wife and kidnapped his daughter, and now Haroun is looking for revenge. Haroun leaves to attack El Akir, but is knocked out by soldiers. They go to Haroun's house, recapture Barbara, and bring her to El Akir. El Akir taunts Barbara with threats of death, but she once again manages to escape, this time hiding out in the Emir's harem. El Akir tries to find Barbara, but she is hidden by a sympathetic harem girl.
Ian eventually tricks Ibrahim into untying his feet, and overpowers him. Ian convinces the bandit to accompany him to Lydda and aid him in his quest for Barbara. Meanwhile, Barbara convinces the harem girl, Maimuna, to help her get out of the castle. It turns out Maimuna is Haroun's long lost daughter and, when she finds out her father is still alive, joyfully agrees to help. Before they can do so, another harem girl, Fatima, betrays them and El Akir bursts in on the two women.
El Akir is about to attack Barbara when Haroun arrives in the nick of time and fatally stabs El Akir. Fatima screams, and two guards burst in. Ian arrives, and he and Haroun subdue the guards. Haroun and Maimuna are reunited, and Barbara and Ian head for the TARDIS.
The Doctor, who has been trying not to get caught up in court politics, attempts to make a break for the TARDIS. He is caught by the Earl of Leicester, who thinks the Doctor is a spy for Saladin. He sentences the Doctor to death. Ian arrives and, presenting himself as "Sir Ian of Jaffa," tells Leicester that the Doctor is a spy and that he is here to carry out the execution. The Doctor plays along and asks for one last chance to see Jaffa before he dies. Leicester agrees, and the Doctor is able to sneak away to the TARDIS with the rest of the crew and leave. When Leicester and his knights see the TARDIS vanish, they agree to keep the story quiet, so as not to look like fools.
On board the TARDIS, the crew enjoy a good laugh over their escape. As the TARDIS prepares to land, the power fails and all the interior lights dim. The crew freeze into immobility.