The Excession is a perfect black-body sphere that appears mysteriously on the edge of Culture space, appears to be older than the Universe itself and resists the attempts of the Culture and technologically equivalent societies (notably the Zetetic Elench) to probe it. The Excession is what the Culture's social scientists describe as an Outside Context Problem, one which a society cannot foresee and is often fatal.
The book's epilogue reveals that the Excession is a sentient entity which is currently acting as a bridge for a procession of even higher beings which travel between universes. It also assesses whether the species and societies it encounters are suitable to be enlightened about some unknown further existence beyond the Universe. As a result of events in the story the Excession concludes that the Culture is not ready for this enlightenment and moves so that it will not cause any further disturbance, hence its disappearance at the end of the book.
A group of stereotypical bureaucrats tries to manage the Culture's response to the Excession but is brushed aside by the Interesting Times Gang, an informal group of Minds some of who are veterans of the Idiran-Culture War, by far the most serious challenge the Culture had previously faced.
Meanwhile a rapidly-expanding race, which the Culture calls the Affront(because of its systematic sadism towards subject species, its own females and junior males, despite being relatively advanced), tries to exploit the Excession by infiltrating a store of mothballed Culture warships and using them to claim control of the mysterious object.
It turns out that the Affront have been manipulated into their grab for power by another Culture faction which thought it was morally imperative to curb the Affront's cruelty by any means, and intend to use the Affront's theft of Culture warships as an excuse for war.
The GSV Sleeper Service eventually takes control of the situation. Its name is the most meaningful pun in the story: outwardly it is an Eccentric (drop-out from the Culture) which dedicates its enormous resources to presenting tableaux of historical events (mainly battles) populated by passengers in suspended animation; but in fact it is a sleeping member of Special Circumstances (the Culture's covert operations division). The name of Sleeper Service is thus double-pronged—it is a Sleeper Service to human beings in Storage, and a Sleeper Servicewithin SC, as it has produced a massive war-fleet during the 40-year period it has spent behaving as an Eccentric. It prepares to deploy this fleet during transit to the Excession.
But Sleeper Service has an unresolved issue. Until a few decades previously, the ship operated under another name as a normal GSV, providing a habitat for a vast number of Culture citizens. Two of its passengers, Dajeil and Genar-Hofoen, had an intense love-affair which ended badly when Genar-Hofoen was unfaithful and a pregnant Dajeil tried to kill Genar-Hofoen. After the break-up, Dajeil froze her pregnancy and subsequently remained in a state of intense depression for 40 years, and the ship changed its name to Sleeper Serviceand started acting as an Eccentric. It carried only one conscious humanoid passenger, Dajeil, and spent a lot of its attention on trying to talk her out of her depression, for which it considered itself partly responsible.
As a result, when the Culture asks Sleeper Service to help in dealing with the threat of war, the ship demands that in return Genar-Hofoen must be handed over to it. Genar-Hofoen is lured to Sleeper Serviceon a pretext, and only later told that he is there to work with Dajeil to help her recover from her psychological trauma.
Sleeper Service then unloads the passengers who had been part of its historical tableaux and converts a large percentage of the mass of the tableaux' scenery into engines. It easily outruns the very fast ship which the Interesting Times Gang had asked to keep watch on it. Once it is beyond the watching ship's sensor range, Sleeper Service changes course and heads towards the Excession. When it arrives it becomes apparent it has previously converted the rest of its spare mass into a vast fleet of Mind-controlled warships numbering in the area of 80,000 units. The Excession, in response to the Sleeper charging at it, then triggers a multi-light-year Gridfire wave which threatens to obliterate it and its entire fleet, along with the accompanying Grey Area. Only its Mindstate, transmitted right at the Excession, saves it by convincing the Excession to halt its attack. The Minds controlling the ships which the Affront stole from the "mothball" store realize they have been tricked, find themselves outnumbered more than 130:1, and refuse to help the Affront. The Affront fleet's commander and the Culture ship which led the conspiracy commit suicide. A prolonged war is thus averted. At the same time the Excession disappears as mysteriously as it arrived.
Meanwhile, the rush of events, combined with a conversation with Genar-Hofoen, results in Dajeil moving out of her depression and completing her pregnancy. Genar-Hofoen returns to the Affront, having been rewarded by being physically transformed into a member of the Affront species (whose company he finds more stimulating than that of the Culture's people).