The Doctor's freedom has been restored, and he offers his old friend Liz Shaw the opportunity to go anywhere in the Universe. She chooses to visit the site of the Siberian explosion of 1908, but instead the TARDIS lands on the docks of St Petersburg in December 1916. The Doctor, Liz and Jo book into the Astoria Hotel to spend a night in history, but when they return to the docks the next day they find that the TARDIS has gone. The Doctor reports the theft to the local police station, where he meets Anya Vyrubova, assistant to the Tsarina. Anya is suspicious of the three British strangers who have arrived unannounced during wartime, but the Doctor claims to be a friend of Ambassador Bertie Stopford and his story checks out. Anya invites him to an audience with Alexandra, whom the Doctor charms with news of her sister in Britain. Alexandra offers the Doctor and his companions rooms in the Winter Palace, while the police search for his stolen "scientific equipment". Their arrival has caused a stir in Russian intelligence circles, however, particularly since they seem to have circumvented the border guards completely. The chief of the Ochrana, Viktor Vasiliyev, bribes British envoy Kit Powell to keep an eye on the strangers and find out what their real agenda is.

Liz is contacted by Kuznetzov, a scientist who specializes in ballistics and who claims to have visited Tunguska recently. Anya, meanwhile, calls on the Empress' most trusted confidant -- Father Grigory Rasputin -- to see the strangers for himself. Liz is repulsed by the uncouth yet magnetic appearance of the man, but Rasputin is more interested in Jo, who seems to react oddly to his name -- as though she'd had a premonition of his fate. The Doctor, meanwhile, is surprised to learn what Kuznetzov has told Liz; according to historical records the first man to visit Tunguska was Leonid Kulik in 1921. Kuznetzov must have lied to Liz to get the opportunity to speak with her -- and he was working on the guns of the warship Aurora, near the site where the TARDIS materialized. What if he saw it appearing from thin air and had it taken away for study?

The Doctor decides to break onto the train which Kuznetzov claimed brought him back from Tunguska in order to find out what his true agenda is, but he is spotted by one of Kuznetzov's fellow agents and Kuznetzov decides to have him killed to be on the safe side. The Doctor is rescued by Kit, who is in fact an agent of British Intelligence playing along with Vasiliyev to lull his suspicions; Kit has concluded that the Doctor is a superior agent, sent to help him find out who has been leaking Russian state secrets to the Germans. While escaping from the assassins, Kit and the Doctor hear them mentioning Kuznetzov while talking between themselves; but what reason could Kuznetzov have for killing the Doctor?

Kuznetzov, having noted Liz's revulsion towards Rasputin, takes her to see Prince Felix Yusupov. Felix hates and fears Rasputin, and believes that the mad monk holds some ungodly power over Nicholas and Alexandra. Felix himself believes he only narrowly escaped Rasputin's hypnotic spell, and is certain that it is Rasputin's influence that is responsible for Russia's deteriorating condition. A man named Arkady Morovich recently jumped to his death from the Volkov rostal for no apparent reason, and Felix believes that Rasputin hypnotised him into committing suicide. Liz agrees that Rasputin is evil, but she's basing her opinion on her first impression of the man, Felix's stories, and her basic knowledge of history. In fact, Morovich's death was an accident -- he'd stumbled across a meeting between Kit and one of his contacts, and although Kit was willing to bribe him into silence, Morovich assumed he would be killed and tried to flee.

Rasputin invites Jo to his home, which she's surprised to find is in the poor part of town; he is still a man of the people. He only wants to hear her stories of travel, the kind which so entranced him as a child; after the death of his infant son, he became a staretz -- a holy wanderer -- in order to see distant places and collect tales of his own. Jo comes to see him not as the evil hypnotic monster of legend, but as an alcoholic man whose legendary magnetism is due mainly to his brutally direct behaviour. He always concentrates directly upon whomever is speaking with him without letting anything else distract him, and this ability may be in part due to a head injury he suffered in his home village when an angry husband stabbed him with a pitchfork. Rasputin doesn't really have the influence everyone believes he does; he simply agrees with Alexandra's own decisions in order to strengthen her belief in herself, and he delights in terrorizing the incompetents who surround his beloved Tsarina by overemphasizing his own importance. When Jo tells the Doctor about her encounter, he admits that the legends of Rasputin were written by those who killed him. In reality the Tsarina trusts him because he saved her son's life, but since news of the heir's haemophilia cannot be made common knowledge, the public does not understand and believes that Rasputin has brought the Tsarina under a hypnotic spell.

The Doctor breaks into Kuznetzov's home, where he finds blueprints of the TARDIS exterior and a drawer full of stolen money. He also intercepts a phone call informing Kuznetzov that "Koba" is ready for him to proceed. The Doctor warns Liz of the possible danger she faces, but Liz is concerned more with Jo's claims about Rasputin, fearing that Jo has fallen under the influence of the evil manipulator of legend. Felix approaches Liz and admits that he and his fellow patriots are planning to kill Rasputin to save the Tsarina from him. He asks her to help lure Rasputin into their hands, assuring her that they will not kill him if he agrees to leave the city and cease exerting his unnatural influence over the Tsarina. Liz considers the offer but intends to refuse, until Kuznetzov approaches her privately, drops his friendly charade and informs her that unless she does as Felix requests, Kuznetzov will have Jo killed.

Kuznetzov, trying to muddy the waters, shows Vasiliyev a forged note which seems to imply that Morovich was murdered because he'd found a connexion between Rasputin and a known German spy. He shows the same note to Felix, who tears it up, knowing it's a forgery and unwilling to risk throwing his entire case against Rasputin into doubt. Kuznetzov then plants stolen money in the Doctor's rooms, arranges for it to be discovered, and reports to Vasiliyev that the Doctor and Kit Powell were seen breaking onto his train. The Doctor is arrested, but Vasiliyev allows him to escape so he will lead the Ochrana to Kit. The Doctor and Kit escape steps ahead of their pursuers, and the Doctor warns Kit of the danger they face; "Koba" is the alias of Josef Stalin, which means that Kuznetzov is an agent of the Socialist Republic fighting section. Despite his uncouth and dangerous behaviour, Rasputin is still seen by many of the common people as one of them, a peasant who has risen in society; and if it is revealed that the aristocracy conspired to murder him, this will spark a revolution. The Doctor and Kit manage to convince Vasiliyev of the truth, aided by the fact that Kuznetzov has just bought a train ticket to the Finnish border, with the intention of lying low in another country until the revolution is over.

Once Liz meets Rasputin in person and has the chance to talk with him, she realizes Jo was right. She has no choice but to pass on Felix's invitation but warns Rasputin to be on his guard. Rasputin, not wanting to alarm his friends, and certain that God will protect him from any murder attempt, tells Anya only that he's been invited to dine with Felix. Anya remains concerned, knowing the hatred Felix feels for Rasputin, and asks Jo to go to the Moika Palace disguised as a maid to keep an eye on things. In the kitchens, Jo sees two men poisoning an entire plate of cakes and dusting several glasses with cyanide. Fearing that she has stumbled across a plot to kill everyone at the dinner, she disposes of the poisoned cakes and glasses and replaces them with untouched ones. Liz is being held prisoner by the conspirators until Rasputin is dead, but she encounters Jo and together they force Kuznetzov's ally Sukhotin to reveal that Kuznetzov has hidden the TARDIS in the abandoned Stock Exchange. They depart to wait for the Doctor, knowing that to preserve history they must wait until Rasputin is dead to alert Anya to their escape.

Felix, struggling with self-doubt and uncertainty, fetches Rasputin and takes him to the Moika Palace, where he offers Rasputin the "poisoned" cakes and glasses. Rasputin wolfs them down with no ill effects, and the horrified Felix, convinced that Rasputin is possessed by the Devil, shoots him in the back as he's kneeling before a cross. Rasputin survives and staggers out into the snow, and Vladimir Purishkevich chases him and shoots him repeatedly in the courtyard. Felix has one of his own dogs shot to provide an explanation for the blood, planning to claim it was an accident at a drunken party. Two policemen arrive to investigate the noise, and Purishkevich drunkenly tells them that he's heroically killed Rasputin and asks them not to report it. Believing that this was an idle drunken boast, the policemen humour him and then return to their station to file their report on a disturbance of the peace. As the policemen go, Felix beats Rasputin's body in a savage fit of uncontrollable rage before the other conspirators can drag him away.

The Doctor and Kit accompany the Ochrana to the train which is just about to take Kuznetzov to the border. Kuznetzov sees them approaching and tries to flee, only to be shot by an over-eager Ochrana agent. As he dies he tells the Doctor that Liz and Jo will soon be implicated in Rasputin's murder, and that the Doctor was wrong all along -- he really had visited Tunguska. The Doctor and Kit rush back to the Moika Palace, knowing that the presence of Liz and will add international implications to Rasputin's murder. As they approach they see two men dumping a body into the frozen Neva River, and the Doctor approaches to see that the victim was Rasputin, trapped beneath the ice -- and still clinging to life. It's possible for the Doctor to save him... but instead he watches as Rasputin drowns, and walks back to Kit, telling him that it was too late.

As dawn breaks, Liz and Jo contact Anya, who passes word on to Vasiliyev and thence to the Doctor. Kit's cover in Russia has been blown, and he accompanies the Doctor back to the Stock Exchange, where the Doctor offers him a trip back to Whitehall in the TARDIS. Kit accepts, and they depart St Petersburg, leaving a Russia which in six weeks will be changed forever.