Stone is a story about a criminal, Ae, who lives in a utopian society, the 't'T', which is spread across a region of space where the density of interstellar objects is sufficiently low that faster-than-light travel is permitted. This society heavily uses nanotechnology, here called 'Dot-tech'. One of the primary uses of Dot-tech is to maintain peoples' health and safety, enabling citizens of the t'T to survive in extreme conditions and making them extremely difficult to kill.
Due to the ubiquitous presence of advanced nanotechnology, the t'T has become something of a post-scarcity society, where every citizen's whims may be easily satisfied. Crime is also virtually non-existent, as all citizens are screened for psychological abnormalities and the Dot-tech satisfies everyone's needs. The few police forces that remain apparently spend more time investigating unusual stellar activity than actual crimes.
Ae has been imprisoned for a crime rarely committed in the society he lives in: murder (mainly due to the difficulty of killing a body protected by nano-tech). He is placed in a high-tech prison (a stone with an artificial environment inside held in the plasma of a sun). He is "executed" by having his Dot-tech purged from his body, which, while not immediately lethal, will eventually cause him to die of natural causes.
He is broken out and picked up by a sub-light ship, where he recuperates before traveling onward, employed by a mysterious agency. During the escape, he is implanted with an artificial intelligence who relays his instructions. The AI reveals that Ae is to kill an entire planet, but does not explain who has ordered the murder, nor their motive for doing so. All Ae is told is that the nature of his mission will be revealed upon its completion.
Ae travels to a planet where he learns the secret of creating black holes. Meanwhile, he meets and travels with a woman named Klabier, and forms something of a romantic connection to her (something uncommon in the t'T), until she reveals herself to be a policewoman. However, Ae escapes before she can detain him.
Ae uses the stolen black hole technology to destroy the atmosphere of his target planet, wiping out its 60 million inhabitants. Upon completing the murder, his directors reveal themselves to be an intelligence that is distributed throughout Dot-tech. The connection involves quantum waveforms, which humans collapse every time they use the Dot-tech, inhibiting its processing power. The Dot-tech cleared the planet of its human inhabitants to create space where they can operate unimpeded (it was necessary to use an unaugmented human for this task, as the Dot-tech's inherent programming apparently prevents them from carrying out the operation themselves).
Unable to cope with the enormity of his crimes, Ae makes no attempt to escape despite being given ample opportunity to do so. Eventually, the police locate him and return him to his prison.
Some large-scale effects of the application of quantum theory are also explored in this novel.