The society of the planet Tara is a mix of the feudal and the futuristic, with a rigid social monarchical hierarchy developed alongside a skill in advanced electronics and android making, which is an ability endowed on the lesser orders. Centuries earlier a plague wiped out nine tenths of the population and the peasants, abandoned by the nobles at that time, began building androids to deal with labour shortages. The planet is now troubled by a struggle for the crown and the power on Tara. The rightful heir, Prince Reynart, is facing a challenge to his rule and coronation from his cousin, Count Grendel of Gracht, a suave but deadly villain who has kidnapped Reynart’s sweetheart, the Princess Strella, and is holding her captive to persuade Reynart not to take the throne.
The Fourth Doctor and Romana arrive on Tara in search of the fourth segment of The Key to Time and, for once, the quest is simple. While the Doctor goes fishing, Romana identifies and transforms the fourth segment alone – it was disguised as a segment of a Grachtian statue – though her luck does not last. She is attacked by a native Taran bear and only saved by Count Grendel, who confiscates the segment as an unregistered mineral and insists that the injured Romana accompanies him to his castle. Once there, it become apparent that Grendel believes she is an android. This assumption is based on her exact physical resemblance to the captive Strella — and Romana too is imprisoned like the Princess.
The swordsmen Zadek and Farrah have meanwhile recruited the Doctor to the party of Prince Reynart. He agrees to help repair an android copy of the Prince which is to be used to help him reach his throne and crown by diverting the attention of Grendel’s men while the real Prince slips into the coronation chamber through a back way. This plot looks plausible, but Grendel strikes first, drugging the Prince’s retinue and kidnapping Reynart himself. When the Doctor and the swordsmen recover they decide to change the original plan and crown the android Reynart instead. The party move through the tunnels beneath the royal castle to get to the throne room so that the facsimile Reynart can be crowned, for if he is not there at the correct moment then Grendel may be chosen under the law to claim the crown. The real Reynart was wounded in his capture and has been imprisoned with Romana at Castle Gracht to prevent any legitimate succession. By their elaborate ruse, the Doctor and his party succeed in getting the android Prince to the throne room and the coronation begins. However, the android Prince is damaged and it is clear the ruse will not hold for long. After the Prince is crowned King, Strella appears and swear loyalty to the King. Although struck by her resemblance to Romana, the Doctor realizes she is an android and hits her on the head with the King's sceptre.
K-9 is enlisted from the TARDIS to provide armed support and scanning intelligence that confirms that the Count has the Prince, the Princess, and Romana in his castle. Shortly afterward, Till, Grendel’s manservant, arrives at the Reynart estate and offers the Doctor a chance to collect Romana from the Pavilion of the Summer Winds, a nearby gazebo. It is, as ever, a trap. Grendel knows the Doctor is the man who has deprived him of the throne and has persuaded his android maker Madam Lamia, who is in love with him, to make an android in the image of Romana that is programmed to kill. While this is happening, the real Romana manages to escape from Castle Gracht and heads off to find the Doctor. She arrives at the Pavilion in the aftermath of Grendel’s attack, which has left Lamia dead, and helps the Doctor flee. The situation is soon reversed as Grendel succeeds in destroying the Reynart android and then recapturing the errant Romana. The evil Count now wishes Romana (as Strella) to marry the real King, who will then be killed, leaving Grendel free to take her hand himself and be declared the legitimate King of Tara.
Worried by the length of time a siege would take, the Doctor resorts to other means to get his friends back from Castle Gracht. K-9 is used to help them gain access to the castle by means of the moat and underground tunnels. The Doctor reaches the throne room just in time to stop the sham Reynart marriage to Romana. He then engages the Count in a deadly fight with electro-swords, defeating him and forcing the villain to jump into his own moat and swim for his survival.
Romana has meanwhile freed Strella and the royal party is united, with Grendel disgraced and presumably on his way to exile. It is a time of reunions: Reynart with his love Strella; and the Doctor and Romana with the fourth segment of the Key and the TARDIS – once K-9 has been retrieved from a boat in the moat.