The year is 64 AD, according to some, and the city of Byzantium in Thrace is governed by the Romans, who rely on fear and the threat of crucifixion to keep the peace. Hieronymous, leader of the Pharisee Jews in Byzantium, faces trouble on several fronts. His advisors Phasaei and Titus have ambitions of their own; the fanatical Zealots, led by Matthew Basellas, intend to destroy all of the Romans who have invaded their homeland; and an irritating sect of heretics continues to spread the world of the false messiah Joshua-bar-Joseph, also known as Jesus of Nazareth. Basellas' brutal plans are opposed by his own brother, Simeon, but Simeon is the only voice of reason amongst the Zealots, many of whom have seen friends and family brutally executed by crucifixion; they will not rest until every Roman is dead.

Meanwhile, the city's praefectus, Thalius Maximus, has just returned from a wearying visit to Rome, where the followers of the corrupt new emperor Nero are destroying Maximus' dreams of a return to the Republic. Maximus' friend and advisor, Gemellus, knows that many of Maximus' problems in Byzantium could be solved if he and General Gaius Calaphilus could find common ground, but they're both too proud and mistrust one another too much for that to happen easily. This is unfortunate, as they have many common enemies. The young and ambitious tribune Marcus Lanilla is plotting with his wife Agrinella and their friend Fabius Actium to dispose of both Maximus and Calaphilus in order to further their own ambitions. Maximus' ex-wife Antonia also poses a potential threat; she has remarried the prominent senator Germanicus Vinicius but has not changed her promiscuous ways one bit. She is also consorting with Agrinella and her fellow conspirators, and is giving them all of the ammunition they will need to bring Maximus down and claim Byzantium for their own.

The TARDIS does not materialise well, but the travellers soon recover from their fall, and the Doctor determines that they are about a day's walk from Byzantium. Barbara is intrigued by the thought of seeing the city, and the Doctor reluctantly decides to indulge her; she claims to have learned her lesson about interfering with history, but the Doctor has visited the Roman Empire before, with Susan, and knows it to be a brutal and bloody place. Nevertheless, he and his friends visit the city, posing as a family of travelling Britons, and as nothing serious happens over the course of the following week, the Doctor eventually admits that his fears seem to have been unfounded. Eventually, the time comes for them to return, and as the Doctor and Ian purchase bread for the day's journey back, Vicki and Barbara visit the temple of Jupiter for one last look. They have arranged to meet in the marketplace outside the temple -- but just as they are within sight of one another, the Zealots attack, infiltrating the crowd and then drawing knives and killing as many Romans as they can strike down.

The travellers are separated in the panic and confusion of the attack. Ian is attacked by a Roman soldier and is forced to kill him in self-defense, but is then struck down and knocked unconscious. Vicki is ushered away from the fighting by a Greek shopkeeper named Georgidias, whose wife Evangeline at first fears that Vicki's presence will draw the Romans to their home and their own daughter Iola. Eventually, she grudgingly allows Vicki to stay in their home for the night, and Georgidias promises to search for Vicki's "family" in the morning once curfew is over. The fighting in the square is soon broken up by a squadron of Romans, in a particularly brutal fashion; when all the bodies are counted, over 160 men, women and children are dead. Basellas counts this a good day's work, and sends his loyal followers to murder Simeon and his wife Rebecca for failing to stand by them.

Ian is found unconscious and is taken to the barracks for interrogation by the cadet trainer Erastus. He withstands the preliminary torture and insists that he is a freeborn Briton, and neither a spy, deserter nor traitor. Calaphilus, who has been to Briton himself, questions Ian and comes to believe that there is truth to his claims. He therefore arranges for Ian to stay in the Villa Praefectus until his story is proven one way or the other, but advises him to be wary; Byzantium can be a dangerous place. Within hours of Ian's arrival, both Maximus' current wife Jocelyn and his maid Felicia attempt to seduce him; however, he spurns their advances, as he does not wish to give his potential enemies any political ammunition to use against him. He soon befriends Gemellus and the librarian Fabulous, who warn him that Jocelyn and Felicia are as nothing when compared to Antonia Vinicius; Ian's going to have his work cut out avoiding them all. Meanwhile, Calaphilus blames Maximus for the uprising, as he'd advised Maximus to take a strong stand by executing hundreds of the Zealots and Maximus had refused. He intends to report to Rome that Maximus' weakness caused the deaths of Roman soldiers, and Marcus and Fabius intend to let him make this report so the general and praefectus will bring each other down without realising who their true enemies are.

Barbara, suffering from concussion, stumbles into a Jewish temple for sanctuary, but the Jews accuse her of being a spy and nearly stone her to death. Hieronymous stops them; he will not stand for this commotion in the Lord's temple, and he believes that Barbara is just an innocent traveller. He therefore grants her sanctuary while she recovers; unfortunately, he is unable to bring her news of her friends, who are missing and presumed dead. Titus and Phasaei try to use Hieronymous' growing affection for Barbara to embarrass him, but she knows enough Old Testament scripture to turn their theological arguments against them; however, she finds it less easy to deal with Hieronymous' daughter Gabriella, who distrusts Barbara and fears that Hieronymous has been blinded by the loneliness he has felt since his first wife's death.

The Doctor has been rescued by the Christians who live in the caves outside the city. As he recovers from the concussion he suffered during the riot, he comes to admire the Christians' fortitude and the elderly Hebron's wisdom. These are first- and second-generation Christians, some of whom knew Jesus' disciples personally; they have settled near Byzantium with copies of the disciples' memoirs and the missionary Paul's letters, which they intend to translate into Greek in order to spread Jesus' "good word", or gospel, throughout the known world. The Doctor eventually recovers, and Aaron and Daniel lead him back to his "carriage", only to find that it has gone. Stuck without his friends or any means of escape, the Doctor settles into gloom, but his troubles come into perspective when he realises that Hebron is dying of cancer. As he resigns himself to a long life stuck on Earth, Daniel returns from the city with terrible news; while protesting the crucifixion of two Christians who had been accused of heresy by the Pharisees, Aaron was killed by a group of Zealots who turned on all of the Christians in the crowd. The remaining Christians decide to flee Byzantium to a place of safety.

Vicki also assumes her friends to be dead, and although Georgidias seems happy to take her in, this is a very different life from the one she's used to. The other Greeks in the community all visit to take a look at the new arrival, and Vicki soon befriends the wise old shepherd Papavasilliou; she is less taken with the tax gatherer Luke Panathaikos, who is denounced by the Greeks as a traitor for collecting taxes for the Romans. Vicki is appalled when Iola warns her to avoid the Roman soldiers at all costs, as they could rape and murder either of them on a whim. One day, when Vicki casually eats a loaf of bread without asking, Evangeline beats her for stealing. Iola tries to cheer her up by taking her to witness the Christians' crucifixion, and Vicki is appalled both by the brutality and the joy with which Iola watches the execution. When the Zealots attack the Christians in the crowd, a Roman soldier spots Vicki watching and tries to assault her; however, Vicki realises that he's deserted his post, and threatens to scream and attract attention. The soldier withdraws, unwilling to face either the penalty for desertion or the murderous Zealots, and Vicki and Iola thus get home safely; but they arrive late, and once again, Vicki is punished for leading Iola astray.

The crucifixion has also affected Ian, whose honesty and honour is attracting attention, both good and bad. Maximus presents Ian with a gladius, a short sword with which he can protect himself, and invites him to share his thoughts on the Christians. Ian has befriended the Christian slaves Dorcas and Tobias, but bearing his own situation in mind he is non-committal -- until he realises that Maximus intends to allow the crucifixion of the Christian "heretics" to go ahead in order to keep the peace amongst the Jews. Despite the risk, Ian lets show his horror and disgust towards this casual attitude to death. Maximus permits the executions, but is impressed by Ian's forthrightness. Ian also manages to impress Calaphilus when he rejects Antonia's sexual advances in no uncertain terms, unaware that the general was hiding nearby, eavesdropping. Greatly amused by Antonia's humiliation, Calaphilus promises to be there should Ian ever need his help. In the meantime, Calaphilus bribes Felicia to lure the tribune Edius Flavia to her bed and then claim he raped her, so that Calaphilus may arrest him and torture the truth of the conspiracy out of him.

Barbara convinces Hieronymous not to attend the crucifixion, but is unaware at first that he has agreed only due to his feelings for her. When Gabrielle returns to berate her father for his blindness, however, Barbara overhears him tell his daughter that he intends to make Barbara his wife. She confronts them both, offended both by Gabrielle's groundless suspicions and by Hieronymous' abuse of her trust; she is grateful to him for sharing his home, but she won't let him take advantage of that gratitude. Bitterly disappointed and humiliated, Hieronymous takes out his frustrations by vowing to persecute the Christian sect to death, and Barbara realises that the time has come to take her leave of him. Though he still feels scorned and rejected, Hieronymous gives his word that no Jew shall harm her while she remains in the city. Barbara thus goes out into the streets of Byzantium, to try to make a new life for herself without her friends, whom she still believes to be dead.

Vicki runs away, unable to handle Evangeline's abuse any longer, but outside the city she meets up with Papavasilliou, and after talking to him for a while she realises that her own arrogance and sense of superiority are contributing to the intolerable situation. She thus returns to the Georgidias home and tries harder to fit in. But she has already drawn too much attention; her neighbours, Damien and Dorothea, have been paid by Centurian Crispianus Dolavia to report anything odd in the Greek sector, and they inform him of the presence of a Briton girl who has been seen watching the Romans and Jews and who must therefore be a spy. Dolavia's men thus burst into the Georgidias home and carry Vicki off before the stunned family can react. After questioning Vicki, Captain Drusus Felinistius concludes that she's an innocent Roman citizen, and promises to punish the Greek family who were holding her prisoner; however, Vicki insists that they meant her no harm and in fact saved her life, and Felinistius thus agrees to let them be. Meanwhile, Dolavia returns to Damien's house to pay him for his services, only to find that Damien and Dorothea have been murdered -- their inevitable fate once someone realised that they were spying for the Romans.

The Christian James, realising that the Doctor needs to occupy himself, takes him to the cave where the scribes Reuben, Rayhab and Amos are converting the scribbled memoirs and letters of the early disciples and missionaries into a set of holy texts. The Doctor is fascinated by the stories, and by the discrepancies shown as each disciple remembered events differently. The Christians' attempt to spread Jesus' gospel have been greeted with hatred and suspicion, but, largely due to the influence of Saul who became Paul on the road to Damascus, Christianity is slowly growing from an obscure sub-sect of Judaism into something much greater. The Doctor helps the scribes to translate their texts from scibbled Hebrew into Greek, advising them to take poetic liberties to breathe life into the words rather than setting down a dry, lifeless version of the facts; these words must inspire as well as instruct. It is the Doctor who finds the vital piece which the scribes had missed -- the opening lines for the first gospel.

Edius withstands the brutal torture of flagellation without betraying his fellow conspirators. Calaphilus secretly respects this, although that won't stop him from continuing to torture him until he breaks. In the meantime, Calaphilus invites Ian to the barracks, and reveals that he is on the trail of a conspiracy which he believes stretches all the way to the praefectus. Ian admits that he's brought Gemellus with him, and together they try to convince Calaphilus that Maximus is not his enemy; in fact, Maximus and Calaphilus may be the only two honourable men in Byzantium, and only by joining forces can they root out the corruption in their midst. The two reluctantly agree to meet, and although there is still mistrust between them -- particularly as Maximus himself appointed Edius to his posting, out of respect for his father -- they do begin to talk, and discover that they have more in common than they'd thought. Meanwhile, the other conspirators learn of Edius' arrest, and fear that he will break under torture. The Zealots have been growing bolder and more vicious now that Simeon is no longer around to hold Basellus in check, and Marcus and Fabius decide to make a stand now; if they kill Basellas, they will become public heroes, and Maximus and Calaphilus will not dare to act against them.

Edius finally gives his co-conspirators' names before dying from his wounds. Calaphilus leads a raid on Marcus' home and arrests Agrinella, but Marcus himself isn't there; he and Fabius are visiting Titus, who has agreed to reveal Basellus' location on the condition that Marcus and Fabius remember Titus as an ally when they control Byzantium. Antonia is also arrested, but Maximus, who still bears some affection for his ex-wife, gives her the opportunity to commit honourable suicide rather than face the humiliation of a public trial and drag her husband's name down with her. Calaphilus then gathers together all of his most loyal soldiers, including Dolavia and Felinistius, issues promotions which will ensure their loyalty, and prepares to initiate purges of those whom Edius named. Meanwhile, the Doctor returns to the Christians' cave, satisfied with the work he has done for the scribes, just as Papavasilliou arrives with bad news; the Christians' spy in Byzantium, the Greek tax gatherer Luke Panathaikos, has just been murdered by the Zealots. However, Papavasilliou also unknowingly brings good news, for when he casually compares the Doctor's zestful attitude towards life to that of a young Briton girl he met recently, the Doctor realises that Vicki must still be alive...

Barbara spends time with a Greek woman named Cressida, and thus learns that Vicki was taken in by the Georgidias family. When she arrives, she is greeted with suspicion at first, but soon Evangeline realises that Barbara is genuinely one of the family whom Vicki had feared lost and thus directs her to the Villa Praefectus. There, Vicki has befriended Felicia, who fears that Calaphilus will dispose of her now that she has served his purpose. Dorcas overhears them, and reveals that she and Tobias have a plan to escape from the Villa and join the other Christians outside the city; however, they will need help, and thus Vicki and Felicia agree to join in their escape. When they emerge from the Villa, they are reunited with Barbara, who was trying to find a way in. As they try to find their way back to the Georgidias home, the purges begin, and the Romans also turn on the Zealots in their midst. As the city descends into chaos, Ian hears about the strange Briton girl in the Villa, and manages to track her down just in time to save his friends from the Zealot Yehwe, whom Ian kills with his gladius. Meanwhile, Phasaei is killed, and the beaten Hieronymous begins to believe that the Christians were right after all. He confronts Basellas, who has been deserted by all of his frightened followers and therefore believes himself to be the true Messiah. Marcus and Fabius find and kill them, but Calaphilus then tracks them down -- and much to the traitors' shock, his loyal soldiers kill them both.

Ian, Barbara, Vicki and their friends shelter in the Georgidias home until morning. Felicia will remain with the Georgidias family, while Dorcas and Tobias try to join the Christians and Ian, Barbara and Vicki return to the TARDIS. As it happens, the Doctor has returned to the city in search of Vicki, just in time to be caught in the middle of the riots; fortunately, he has survived, and while leaving the city he runs into Dorcas and Tobias. The travellers are thus all reunited at the place where they left the TARDIS; according to rumour, the strange blue box was taken to the villa of Senator Germanicus Vinicius, which means that they'll have to walk all the way to Rome to get it back. Ian regrets only that he didn't get the chance to bid farewell to Maximus or Calaphilus before his departure. The travellers set off, knowing that they have a long and difficult journey ahead, with no guarantee that they will find the reward they seek at the end of it. But the same can be said for the people of Byzantium.