Deucalion was first published in Australia on 1 September 1995 by the University of Queensland Press in trade paperback format.^[1][2] In 1996 it was published as an audiobook by Louis Braille Books and in 2002 it was released in the United Kingdom by Flyways. It has also been distributed to North America by International Specialized Book Services.^[3] Deucalion joint won along with Garth Nix's Sabriel the 1995 Aurealis Award for best young-adult novel and was a short-list nominee for the 1996 Children's Book Council of Australia: Book of the Year, Older Readers award.^[2][4]

The novel opens in the late 23rd century AD, by which time, humanity has explored light years out into space. However, only one habitable planet has been discovered, named Deucalion. Deucalion is 34 light-years away from Earth, with one large continent and an inland sea. Deucalion has a native sentient population, named the Elokoi, similar to H.G Wells' Eloi from The Time Machine. The Elokoi are at a level of civilisation similar to the Stone Age. Both Human and Elokoi settlements are only on the east coast of the continent, however, human settlers have forced the Elokoi to live on reservations. The human capital is called New Geneva.

Though having developed interstellar travel, spaceships can still only travel at the speed of light, and no faster, so it takes thirty-four years for even the fastest of ships to reach Deucalion. Passengers on board ships have to be cryogenically preserved.