It was written while his first Discworld book, The Colour of Magic, was undergoing publication, and was intended as a potential starting point for another novel. The Colour of Magic, however, was very successful, causing him to put the story aside in favour of writing a sequel to that.
Larry, using his array of antennae, discovers that two people have arrived on his Earth. He ambushes one of the newcomers, a man named Joshua Valienté, and takes his belt - the device that allows humans to "move" between alternate Earths - as well as his gun.
Valineté tells Larry that Forward Base, a government-run station in the high meggas, was poisoned. Everybody who worked there was killed, apart from him. He says that he's been chased across alternate Earths by the murderer - the other person that Linsay had detected.
Larry ties up Joshua Valientè. He finds the other individual, Anna Shea, unconscious in a crater. When she moved into Larry's Earth, she fell into a crater which hadn't been present in the previous Earth.
The crater was made by a fragment of an asteroid that hit Linsay's Earth - as well as the surrounding worlds - ten or fifteen thousand years previously. Larry calls this asteroid "the Fist".
He returns to Joshua with Anna Shea over his shoulder. Valientè, still tied up, is observing a pack of intelligent superbaboons - Larry tells him that he calls the leader of the group "Big Yin".
They travel to Larry's stockade, where Shea regains consciousness. She tells him that Valientè was the one who poisoned Forward Base, not her.
That night, a security beam that Linsay had rigged inside his tent is triggered. Waking up, he moves one world back and runs, trips and injures his leg. The next morning Shea tells him that she was the one who entered his tent; she had intended to persuade him that she wasn't the murderer.
Valientè flees the stockade, a belt in hand. Larry shoots him, wounding him. Shea asks for the gun, so that she can finish him off - an act of murder. Larry realises that she is a killer, and therefore must have been the one who poisoned Forward Base.
Shea sees what Linsay has realised and attacks him. He uses his belt to move up the chain of Earths, Shea following close behind. With every move, the effects of the Fist become more pronounced. Finally, Linsay and Shea move into the Gap - a world where the Earth has been destroyed completely.
They find themselves in outer space. Larry, who knew of the Gap's existence, quickly moves back one Earth to safety and passes out.
He wakes up in his stockade, being looked after by Joshua Valientè. Anna Shea appears suddenly, holding a gun - she also survived the Gap. Big Yin, the superbaboon pack leader, assaults her from behind and Shea is killed.