The glory days of the Skonnan Empire are long since past, but many of its citizens and soldiers yearn for conquest. The arrival of the mysterious horned Nimon on Skonnos brought hope of imperial restoration. The fearsome creature from within its labyrinth has promised to rebuild the Empire providing it receives a series of tributes from the Skonnans and their fawning, arrogant leader Soldeed. This tribute is to comprise groups of youthful sacrifices from the nearby planet Aneth, as well as a supply of hymetusite crystals. Young people have thus been abducted and transferred to the labyrinth. On the final collection, however, the interstellar craft bearing the sacrifices breaks down in space. The ancient war craft has worn out, and when the co-pilot over extends the engines, the Pilot is killed when a control panel explodes.
The Doctor, Romana and K-9 are in the TARDIS console room where he is making modifications to the ship. Various controls are disconnected, but unfortunately the area of space he has chosen to materialise the ship in is close to a manufactured Black Hole and they are in danger of being drawn in. He extends the TARDIS door force field to a nearby spaceship – the Skonnan battle cruiser – and he and Romana board the warship. Once aboard the Doctor notices an abundance of radioactive hymetusite crystals, and soon finds a hold full of young prisoners. They are from Aneth, and one, Teka, has a seemingly misplaced faith in another prisoner, Seth, to free them from their incarceration. The Co-Pilot investigates the hold and discovers the Doctor and Romana. He takes them to the bridge at gunpoint and forces them to fix the ship. Romana suggests adapting the ship to use a hymetusite crystal power source, and one is brought to her while the Doctor returns to the TARDIS to gather supplies. Aboard the TARDIS the Doctor learns from K-9 of the collapse of the Skonnan Empire in civil war.
With the Skonnan craft repaired the Co-Pilot starts to move his ship away; the TARDIS is stranded and facing obliteration in the vastness of space. The Doctor bounces the TARDIS off the approaching asteroid and starts to repair the console in order to pilot the ship to Skonnos and confront the evil there. The planet is dominated by the Nimon, which exists within its labyrinthine Power Complex into which only Soldeed may venture. The Nimon is angry when Soldeed reports that the last batch of sacrifices have not arrived and says it will withhold the arms that will help rebuild the Skonnan Empire.
Soldeed emerges from the Power Complex and hears from his guard captain Sorak that the ship has been found. It arrives on Skonnos and Soldeed leads the party of greeting, being unnerved to see Romana aboard. The Co-Pilot lies that she is the cause of all the problems on the ship, being a pirate who stole aboard and killed the Captain. Soldeed does not believe this and then forces the Co-Pilot into the Nimon Power Complex where he faces certain death. Moments later Romana and the Anethans are loaded up with hymetusite and sent into the maze. The TARDIS materialises in the central square of Skonnos and the Doctor is taken to Soldeed. He soon escapes, and heads into the Power Complex to escape his pursuers.
Deep in the Complex – whose walls seem to shift and change creating various labyrinthine patterns that all lead to the Nimon – Romana finds husks of previous Anethans, drained of life. The Co-Pilot also arrives, still pleading for his life, and when the Nimon appears it despatches the desperate soldier first before turning its mighty horns on Romana and the cowering Anethans. The Doctor arrives and distracts the Nimon, saving Romana, Seth and Teka who run after him. The other Anethans are too scared to leave.
The Nimon has reached the power source room and starts manipulating the controls of the machine, which causes the Complex to glow with energy. A shimmering tunnel appears, and a travel globe bearing two more Nimon comes down it. They announce that the planet Crinoth is dying and that all the Nimon must continue the Great Journey of Life to Skonnos. Once the Nimon leave the Doctor examines the globes: they are travelling vessels that have journeyed down a tunnel set between two black holes. The Doctor accidentally sends the globe down the tunnel with Romana in it but before he can reverse this Soldeed arrives and uses his staff to destroy the control panel.
Romana arrives in the dying world of Crinoth and encounters many Nimon and a broken old man named Sezom, who helped the Nimon establish themselves on his world and now knows they have destroyed it. He has also discovered that when jacenite is integrated into the staff that he was supplied with by the Nimon, it has the ability to stun them. He gives Romana a piece, but is killed by a Nimon while helping her to escape.
Seth shoots Soldeed unconscious and the Doctor attempts to repair the transportation system. Just as he is about to complete the repairs, the Nimon return to the power source room and restrain him. However, they then reverse the tunnel, which brings Romana back from Crinoth. Romana tosses the jacenite to Seth, who now has possession of Soldeed's staff, and he uses it to stun two of the Nimon. Having managed to free himself from Soldeed's laboratory, K-9 arrives in time to deal with the remaining one. Soldeed, having escaped from the power source room, has seen the multiple Nimon and his faith is badly damaged. He is shot down by Seth but manages to trigger a chain reaction which will destroy the Complex. The Doctor and his party make their way out, using K-9 to work out a proper exit path through the labyrinth. They escape and join up with the remaining members of the Skonnan military council, all of whom evacuate the main square as the Nimon Power Complex explodes.
Later in the TARDIS the Doctor watches as Seth and Teka pilot a spacecraft away from Skonnos, having been granted their freedom. Elsewhere Crinoth can be seen disintegrating. It seems that the Nimon threat is over.