In the previous novel, 2010: Odyssey Two, Jupiter was converted into a mini-sun which was dubbed "Lucifer" following the Soviet ship Leonov’s mission to Jupiter to find out what happened to the Discovery. A message was sent to Earth by Dave Bowman, through HAL: "ALL THESE WORLDS ARE YOURS, EXCEPT EUROPA. ATTEMPT NO LANDINGS THERE." (The movie version adds the words "USE THEM TOGETHER. USE THEM IN PEACE", as part of its heightened Cold War emphasis.) This is due to the discovery of alien life in Europa's ocean, which was frozen over at the surface until Lucifer melted the ice and caused an atmosphere to form.
Between 2010 and 2061, there have been several advancements, both technological and political. The USA, USSR, and China are now at peace with each other, all nuclear weapons are now under international control, and there is now a Planetary President (a former monarch, Edward VIII — his country of origin is not specified). The black population of South Africa had rebelled in the 2030s and formed the United States of Southern Africa (USSA). The white population of South Africa had seen this coming and mostly fled to Europe, taking most of the country's wealth with them and leaving the black population to rebuild the economy, which they did in a matter of weeks by use of diamonds (it is worth noting that this book was published in 1987, at which time South Africa was still federated and apartheid was still in force). In the wake of the breakthrough discovery of a new form of muon-catalyzed fusion, space travel has undergone many startling advancements; with the advent of fusion-powered spacecraft, large-scale interplanetary travel is now commercially viable. The largest such corporation is Tsung Spacelines, run by Hong Kong billionaire Sir Lawrence Tsung (the manufacturers of the crafts Cosmos, Galaxy and — most recently — Universe).
Strangest of all, there has been a startling development on Europa: an enormous mountain has sprung up out of nowhere. No one is sure of the origin of "Mount Zeus"; being asymmetrical, it cannot be a volcano.
Meanwhile, there is a team of scientists on Ganymede who are working on terraforming the former moon. Scientist Rolf van der Berg, a second-generation Afrikaner refugee, studies pictures of Mount Zeus and determines that it is in fact one enormous diamond. He communicates his discovery to his uncle Paul Kreuger, speaking in Afrikaans as a security measure because it is now an endangered language, and decide that van der Berg will get aboard the Galaxy on their flyby of Europa in order to try and see if he is correct. However, their exchange is discovered both by SHAKA (a secret militant organization in the USSA, named for Shaka) and ASTROPOL (similar to Interpol). SHAKA sends an operative called Rose McCullen onto Galaxy undercover as a steward, and an unknown organization — presumably ASTROPOL — approaches Chris Floyd II on Ganymede and tells him to "keep his eyes open."
As Galaxy nears Europa, Rose McCullen delivers coffee to the bridge and then hijacks the ship, sealing the cockpit and ordering Second Officer Chang at gunpoint to pilot Galaxy down to the moon's surface, where, after Chang does not exactly follow Rosie's directions, it splashes down into Europa's ocean, the Sea of Galilee. Having essentially accomplished her mission, Rosie then shoots herself. Other crew members throw her body overboard: a large creature rises to the surface of the ocean, swallows the body, vomits, and dies. The crew conclude that Europan biology and Earth biology are incompatible: they won't be able to forage there after exhausting the ship's stores.
Universe receives the news that Galaxy is marooned on Europa, and that they need to undertake a rescue mission. After fueling itself from a geyser on Halley's Comet, Universe heads for Europa.
Meanwhile, Galaxy’s Captain Laplace steps down for the acting captain Lee, who is a professional sailor. Lee pilots Galaxy through the water to come to the shore of a small—and rather dismal—island named Haven. Captain Laplace takes command again, and accepts the suggestion that Rolf van der Berg and Chris Floyd II take the shuttle William Tsung or Bill Tee (named after Sir Lawence Tsung's son William) to study Mount Zeus, the wreck of the Chinese spacecraft Tsien and the enormous monolith lying on its side at the border between the dayside and nightside, dubbed the Great Wall. Van der Berg and Chris take the Bill Tee to Mount Zeus. Up close, van der Berg relays a message to his uncle Paul through Ganymede stating "LUCY IS HERE", verifying that Mount Zeus is indeed one large diamond. The code word "Lucy" was chosen both in reference to the mini-sun Lucifer and to an article in the journal Nature in 1981 hypothesizing that the cores of Uranus and Neptune were in fact diamonds the size of Earth (caused by the compression of carbon), with the hypothesis making a logical extension to Jupiter. The article was subtitled "Diamonds in the Sky?" in reference to the Beatles song "Lucy in the Sky with Diamonds". Mount Zeus is a fragment of Jupiter's core which survived the creation of Lucifer and later impacted on Europa.
On the Universe, the celebrity guests discuss the mystery surrounding Dave Bowman and the monoliths, and whether they would be allowed to land on Europa to rescue Galaxy’s crew. Floyd follows Yva Merlin's suggestion that he simply try to call Bowman on the radio, and that night has a strange dream in which he sees the monolith floating at the foot of his bed.
The Bill Tee flies by Tsien, which has been completely stripped of its metals, and on to the Great Wall. In the shadow of the Great Wall they find a deserted Europan village made up of igloo-like structures. An image of Heywood Floyd appears to Chris in the same way that Dave Bowman appeared to Floyd in 2010, telling him that the Universe was coming and that the Europans had left until "the wind blows the poison away." Van der Berg thinks that Chris is crazy until he realizes that the heat of the engine cracked the steam exhaust of the Bill Tee into hydrogen and oxygen, oxygen being poisonous to Europans. The shuttle's fuel is expended so they wait there until the Universe arrives.
Chris contacts Universe and finds that his grandfather is not dead at all, but alive and well. The crew are rescued and brought to Ganymede, where they watch via satellite as Mount Zeus, which has been steadily sinking, finally disappears beneath the Europan surface. Soon thereafter, Paul Kreuger writes a follow-up article for Nature (80 years after the original article's publication), stating that Mount Zeus was a mere fragment of Jupiter's core and it is almost certain that many more such large pieces of diamond are currently in orbit around Lucifer, and proposing that a program be initiated immediately to collect these enormous quantities of diamond and put them to use.
Floyd and Chris II become close again, and both become friends with van der Berg. They talk about how Floyd called Bowman on the radio, and Chris asks "Did you ever get a reply?" Floyd almost tells his grandson about the monolith in his cabin, but does not after rationalizing that it was probably a dream.
In the epilogue, the star Lucifer stops shining in 3,001, and in Manhattan "the monolith awakes" (referring to the original monolith discovered on the moon in 2001, and which was taken to Manhattan as a monument). It is also indicated that humans have found more quantities of diamond from the former Jupiter and used it to create space elevators and an orbital ring connecting them, as suggested by Paul Kreuger in his article. (This idea will later be a central concept in 3001: The Final Odyssey.)
Shortly after the novel was released, Tom Hanks expressed great interest in producing a film adaptation, with himself cast in the role of Floyd, and Keir Dullea and Douglas Rain reprising their roles as David Bowman and HAL 9000. These plans never went beyond the initial announcement.