Nine years have passed since the failure of the Discovery mission to Jupiter in 2001, which left commander David Bowman, Keir Dullea, and his crew missing. Amid rising international tensions, the United States and the Soviet Union each prepare separate missions to Jupiter. The Soviet spacecraft Leonov will be ready a year before the American Discovery Two, but only the Americans can reactivate HAL 9000, Douglas Rain, the ship's sentient computer thought to be responsible for the disaster. Because Discovery will crash into Jupiter's moon Io before the Americans can reach it, the Soviets agree to bring along former NCA Director Heywood Floyd, [Roy Scheider], Discovery engineer Walter Curnow, [John Lithgow], and HAL's creator Dr. Chandra, [Bob Balaban].
Arriving at Jupiter, Leonov detects chlorophyll on Jupiter's icy moon Europa. A probe sent to investigate is destroyed by an energy burst when it reaches the source of the chlorophyll, a danger Floyd interprets as a warning to stay away from Europa. After aerobraking in Jupiter's atmosphere, Leonov enters orbit around Io and encounters Discovery. Walter Curnow and cosmonaut Maxim Brailovsky, [Ilya Baskin], spacewalk to and enter the derelict vessel. Both men suffer panic attacks for different reasons, but they bond over the shared experience and become friends. Curnow restores Discovery's power and propulsion, and Chandra reactivates HAL, who then helps steer the ships toward a giant monolith located at the Lagrange point between Jupiter and Io. Brailovsky approaches it in an EVA pod, but is killed when the pod is destroyed by an energy burst.
On Earth, Bowman, now a noncorporeal being, appears through his former wife's television to say goodbye, telling her that something wonderful is going to happen:
> something wonderful is going to happen
He then visits his comatose mother in a hospital, and she awakens, seemingly aware of her son's presence. The unseen Bowman brushes her hair, and after he departs, she dies peacefully. Dr. Chandra reveals the reasons for HAL's malfunction: the National Security Council ordered HAL to conceal information about the monolith from Discovery's crew, a demand that conflicted with HAL's basic programming and triggered a paranoid breakdown. When Bowman and co-pilot Frank Poole discuss deactivating HAL, the computer concludes that the human crew is an endangerment to the mission and terminates them. Chandra believes Floyd’s signature on the order is tied to the political pressure back on Earth, though Floyd denies any knowledge of the directive.
A political crisis on Earth brings the United States and the Soviet Union to the brink of war. The Americans are ordered to abandon Leonov for Discovery, and both ships plan to depart Jupiter in the coming weeks. Floyd warns that time is short and that HAL might prioritize the mission over the crews' safety, but Chandra reveals to HAL that the crews are in danger and that both ships could be destroyed. HAL thanks Chandra for telling him the truth and proceeds with the escape plan. When Discovery’s fuel runs dry, Leonov separates and fires its own engines, enabling the two crews to begin their evacuation.
Bowman asks HAL to transmit a message to Earth. The monoliths engulf Jupiter, triggering nuclear fusion and turning the planet into a new star. Before Discovery is destroyed, HAL sends this message:
