In 2287, Kirk, Spock and McCoy are enjoying shore leave on Earth at Yosemite National Park when suddenly their vacation is interrupted by an emergency call to duty by Starfleet Command. Kirk and his friends learn that the Klingon General Korrd, Romulan Caithlin Dar and Federation counsel St. John Talbot are being held hostage on the planet Nimbus III, the planet of galactic peace. The new U.S.S. Enterprise 1701-A warps to investigate the situation.
Meanwhile, on a nearby Klingon Bird-of-Prey, Captain Klaa learns of the mission of the U.S.S. Enterprise and the hated Kirk and sees an opportunity for advancement in the Klingon ranks. In an effort to intercept the U.S.S. Enterprise, he orders the ship to Nimbus III.
The U.S.S. Enterprise is the first to arrive at Nimbus III and Kirk sends a shuttlecraft and landing party to the planet's only town. It is soon discovered that the town is held by a band of scruffy colonists led by a telepathic insane Vulcan, Sybok. In addition, the team learns that the hostage situation was just an elaborate ruse to obtain a Federation starship. Sybok believes that his destiny, the discovery of Sha Ka Ree, meaning "heaven" in Vulcan, has finally been fulfilled, but he needs a starship for transportation. Sybok forces the shuttlecraft to take his people to the U.S.S. Enterprise, where he fights with Kirk for control. Strangely, Spock has the opportunity to kill the insane Vulcan, yet he doesn't. Forced to explain his actions, Spock reveals that Sybok is his half-brother, exiled from Vulcan for choosing emotion over logic. Family relations aside, Kirk and the rest of the crew are thrown in the starship's brig.
Scotty finally helps Kirk, Spock and McCoy escape from the brig and sends an urgent message to Starfleet. But the message is intercepted by Vixis, Klaa's first officer.
In an effort to gain valuable followers, Sybok uses his powers to reveal to McCoy and Spock their inner-most pain, then helps each "heal." Kirk, however, refuses to allow the Vulcan to use his telepathic powers. Sybok is angered, yet he knows that he needs Kirk to pilot the Enterprise to "Sha Ka Ree," and thus a reluctant truce is declared.
The starship then sets course for the center of the galaxy, a mythical planet bound by an energy field — the Great Barrier. Sybok and the captured crew are successful in penetrating the barrier, and find a small blue planet. Sybok takes a landing party to the planet's surface, where he suddenly calls out to God. In a blinding flash of light, an entity appears, questioning him about the U.S.S. Enterprise. When Kirk asks why a god would need to ask such mundane questions, he is stricken down with bolts of electricity. McCoy brusquely tells Sybok that he has trouble believing in a god who enjoys inflicting pain. This seems to affect Sybok, and the Vulcan slowly begins to doubt his own quest. Afraid that the entity might be let loose in the galaxy, Sybok tries to use his telepathic powers to make the creature realize its own pain. The two grapple and mysteriously disappear underground. Convinced that the entity must be destroyed at all costs, Kirk orders a photon torpedo be fired at the planet. The U.S.S. Enterprise transporter can only bring up two crewmen at a time, so Kirk sends McCoy and Spock. With Kirk left all alone on the planet's surface, the enraged being suddenly appears and tries to destroy the Captain for ruining its plans of escape, via the starship, and subsequent galactic conquest.
Just then, Captain Klaa's ship arrives and uncloaks to fire on the U.S.S. Enterprise. Spock demands that the first officer, General Korrd, pull rank and beam Kirk up to the Klingon warbird and fire upon the mysterious being. Spock transfers with Korrd to the Klingon ship in order to insure that his "suggestion" is carried out.
With Kirk saved and the evil entity destroyed, there is a reception on board the Enterprise to celebrate this unusual Klingon-Starfleet cooperation. Scotty and Korrd enjoy drinks while Klingons cautiously mingle with U.S.S. Enterprise crew. McCoy suggests that the Great Barrier is in place to keep the entity boxed in, not to keep others out, which implies an even greater being at work.
Having saved the galaxy yet again, the three officers return to their interrupted vacation at Yosemite.