The events of the novel are a direct continuation of those in the preceeding Discworld novel, The Colour of Magic.
Warning: Wikipedia contains spoilers
After the wizard Rincewind has fallen from the edge of the Discworld, his life is mysteriously saved as he lands back on it.
Meanwhile, the wizards of Ankh-Morpork discover that the Discworld will soon be destroyed unless the eight spells of the Octavo are read: The most powerful existing spells, one of which hides in Rincewinds head.
Consequently, several orders of wizards try to find Rincewind and kill him, lead by Trymon, a former classmate of Rincewind's, who wishes to obtain the power of the spells for himself.
After Rincewind, who has met again with Twoflower, escapes them, it becomes apparent that Great A'Tuin, the giant turtle that carries the Discworld, has set a new course that leads it directly into a red star with eight moons. Rincewind and Twoflower are accompanied by Cohen the Barbarian, an aging hero; and Bethan, a sacrificial virgin saved by Cohen, with assistance from Rincewind and Twoflower.
As the star comes nearer and the magic on the Discworld becomes weaker, Trymon tries to put the seven spells still in the Octavo into his mind, in an attempt to save the world and gain ultimate power.
However, the spells prove to strong for him and his mind becomes a door into the "Dungeon Dimensions", from where strange, horrible creatures try to escape into reality.
After winning a fight against them, Rincewind is able to read all eight spells aloud - whereupon the eight moons of the red star crack open and reveal eight tiny world turtles that follow their parent A'Tuin on a course away from the star. The octavio is then eaten by Twoflower's luggage chest.
The book ends with Twoflower and Rincewind parting company, as Twoflower decides to return home; leaving his luggage chest with Rincewind as a parting gift.