The White Guardian recruits the Doctor to collect the six hidden and disguised segments of the powerful Key to Time. He assigns him an assistant Time Lady named Romanadvoratrelundar, whom the Doctor calls Romana (despite Romana's preference for "Fred" when given a choice by the Doctor). He warns him that the Black Guardian also seeks these segments, but for an evil purpose. The White Guardian provides them with a wand-like device which can locate the pieces and remove their disguise. When inserted into the TARDIS console, the locator reveals a segment to be on Cyrrenhis Minima, but then the signal moves to Ribos.
Ribos is an icy planet with late-medieval-type inhabitants who are unaware of alien cultures. A human from Earth named Garron tries to sell Ribos to an exiled tyrant called the Graff Vynda-K. The Graff is impressed by the planet's supposed quantity of jethrik, the rarest and most valued mineral in the galaxy. He believes the opportunity confirmed when he sees a piece of jethrik besides the Ribos crown jewels. This is all part of a ruse orchestrated by Garron; the jethrik was planted by Garron's assistant Unstoffe, who also (playing a native with an "honest face") spins a yarn to the Graff about a nearby lost mine. The locator points the Doctor and Romana to the same jethrik, which must be the disguised segment of the Key to Time.
The Graff Vynda-K provides a large sum of money, as a deposit for the planet, that is to be kept safely in the room with the crown jewels, watched by Ribos guards by day and a shrivenzale beast by night. Later, Unstoffe distracts the shrivenzale, recovers their piece of jethrik, and takes the money from the safe. The Graff learns of Garron's deception when he discovers a covert listening device in his room. He takes Garron hostage with his "accomplices" the Doctor and Romana, and he starts the search for Unstoffe, who still has the money and the jethrik. Unstoffe hides with Binro, a homeless outcast who believes that Ribos is a planet orbiting a star, which Unstoffe confirms to be true. The Ribos guards summon a Seeker who locates Unstoffe's hideout. Using the listening device in the Graff's room, Garron warns Unstoffe about the Graff. Binro, thankful for Unstoffe's encouragement, leads him to the labyrinthine Catacombs under the city.
The Graff and his men enter the Catacombs without the Ribos guards, who fear the place. K-9 helps the Doctor, Romana, and Garron to escape from the Graff's quarters and go to the Catacombs. The Ribos guards destroy the entrance to the Catacombs causing the ceiling to collapse on the Graff's men. With the money and the piece of jethrik, the Graff gives his last surviving guard an explosive to kill himself with. The guard, actually the Doctor in disguise, swaps the explosive for the jethrik. The Graff walks off into the maze yelling like a madman before exploding. After leaving the Catacombs, the Doctor, Romana, and K-9 dematerialise in the TARDIS. Garron and Unstoffe are free to the Graff's deserted ship and the Doctor and Romana reveal the first piece of the Key to Time.