• James T. Kirk: William Shatner
• Spock: Leonard Nimoy
• Leonard "Bones" McCoy: Deforest Kelley
• Chekov: Walter Koenig
• Sulu: George Takei
• Uhura: Nichelle Nichols
• Kahn: Ricardo Montalban
• Lt. Saavik: Kirstie Alley
• Dr. Carol Marcus: Bibi Besch
• Dr. David Marcus: Merritt Butrick

"Captain" Saavik, a Vulcan lieutenant in Starfleet, manages to lose to the Kobayashi Maru simulator's preprogrammed no-win situation, like every other cadet ever to take the test (with a single exception). Spock, now Captain of the Enterprise, returns to the ship to prepare for Kirk's upcoming pre launch inspection after dismissing the students from the simulator exercise. Kirk returns home and is visited by Dr. McCoy, who, after presenting him with a birthday present, tells Kirk that his abilities are wasted on a desk job and that he should resume his command of a starship.

USS Reliant, on assignment searching for lifeless planets as potential test sites for the top secret Genesis project, arrives at Ceti Alpha V. Beaming down, Captain Terrell and his first officer, Commander Chekov, discover a series of cargo bays formerly of the SS Botany Bay, a vessel full of genetically engineered supermen from late 20th century Earth led by the cunning Khan. Chekov urges Terrell to return to the Reliant, but they are captured by Khan and his followers. Khan, after fifteen years, is still seeking revenge against Kirk for exiling the Botany Bay's crew. Khan infests Chekov and Terrell with Ceti eels, which affect the brain and make their victims susceptible to suggestion, although the eels' victims will eventually go mad and die painfully. Khan hijacks the Reliant and has Chekov contact space station Regula 1, where the Genesis project is being developed by Dr. Carol Marcus, an old flame of Kirk's, along with a team of scientists including her son David. Chekov says that Kirk has ordered the Genesis device to be transferred to the Reliant upon arrival for immediate testing. David Marcus fears the worst, always suspicious of Starfleet's motives concerning the Genesis project. Carol contacts Kirk while the Enterprise is on a cadet cruise. Kirk takes command of the ship and sets it on a course to the station.

En route, Kirk, Spock and McCoy review a presentation prepared by Carol which reveals that the Genesis "torpedo" is a device which will, when fired on a lifeless planet, restructure it into a verdant, life-supporting world ready for colonization. The Enterprise arrives at Regula 1 and is fired upon by the Reliant, which, since the shields were not raised in the presence of a presumably friendly ship, causes critical damage to the Enterprise and kills many of the unprepared cadets. Khan reveals himself and demands that Kirk surrender himself, but Kirk bluffs Khan into giving him time to consider. Kirk overrides Reliant's shields by remote control and returns fire, forcing Khan to retreat. Kirk, Saavik and McCoy beam down to the space station, finding most of the scientists slaughtered and the Genesis device missing. They do find Chekov and Terrell, apparently left for dead by Khan although the Reliant officers are actually keeping an eye on Kirk for their master. Deducing that the Genesis team must have had an underground test site on the dead planetoid Regula that the station orbits, Kirk gambles on beaming down into the surface under the station. There, they find the Genesis device, but are ambushed by David and one of the other scientists. Terrell kills the other scientist, and then contacts Khan, who orders Terrell and Chekov to kill Kirk. Terrell goes mad and kills himself, while Chekov collapses and the Ceti eel vacates his body. Khan beams the Genesis device up to Reliant. McCoy begins tending to Chekov as Kirk and Carol discuss why David - their son - remained with Carol and became a scientist himself. They all go deeper into the test area and find a lush cave with vegetation and a waterfall, created by a fraction of the Genesis device's power. Kirk then reveals to Saavik that he became the only cadet in history to beat the Kobayashi Maru test by reprogramming the simulator, which elicits a comment from David that Kirk has never had to deal with death on a personal basis. Reliant returns to the station after makeshift repairs, but the Enterprise is nowhere to be seen.

The Enterprise, apparently contradicting the repair estimates of an earlier communication between Kirk and Spock which Kirk realized that Khan would be eavesdropping on, arrives and retrieves Kirk and the others while hiding behind the other side of Regula. Kirk orders the ship into the nearby Mutara Nebula, where sensors of both ships will not function. Khan is unable to resist the chance to pursue, and plunges into the nebula behind the Enterprise. In the ensuing battle, the Enterprise's warp drive is damaged. Sulu manages a few lucky shots of his own, crippling the Reliant and killing most of Khan's crew, but the dying Khan is unwilling to admit defeat and prepares to detonate the Genesis device at point blank range, which will destroy both ships. Scotty is unable to repair the engines, and Spock rushes to engineering without a word to anyone (except for what seems to be a very quick mind-meld with Dr. McCoy), forgoing safety precautions and entering the radiation-saturated engine chamber to repair the warp engines. When Spock finishes his task, Kirk orders the ship out of the nebula at top speed. The Reliant explodes, initiating the full Genesis effect on Regula, as Kirk, receiving a message from McCoy, hurries to engineering only to see Spock die from massive radiation poisoning. Spock's body is loaded into a torpedo casing, which is fired at the Genesis planet. David admits that he may have misjudged Kirk and says he is proud to be his son, while the crew reflects on Spock's sacrifice and the marvel of Regula's transformation into a world of its own.