The story that made it to the screen began with a prophet, a man riding in the desert, with a plan to find God.

While the inner workings of the new starship Enterprise are being completed in earth orbit, much of the bridge crew is on shore leave below. Kirk is free-climbing the El Capitan in Yosemite National Park. Spock is apparently playing with a levitation device (reminiscent of Commando Cody's jet backpack, from the era of space opera serials that included Zombies of the Stratosphere, featuring a quite young Leonard Nimoy) and hangs suspended in the air chatting with Kirk, causing him to fall, and then to be rescued in the nick of time by Spock. McCoy is watching the whole show through binoculars, which inspires his timeless line, "You really piss me off, Jim."

But meanwhile on the remote "planet of Galactic peace," a desert wasteland, the prophet with strange powers to affect minds and hearts plots to bring a starship there, to complete his holy mission. The starship is the Enterprise, the mission is to find Sha Ka Ree, the fabled planet of God. The prophet is Sybok, a Vulcan who turned against his culture's insistence on "logic," because he believed the way to truth was through feeling. He also turns out to be Spock's half-brother.

Sybok captures the Federation, Klingon and Romulan representatives to the planet of peace, in the hellhole known as Paradise City. When Captain Kirk and the Enterprise rescue them, they turn out to be Sybok converts and co-conspirators. Soon most of the crew sides with them.
The Enterprise confronts the Great Barrier at the center of the galaxy, and passes through it, an apparent miracle. Kirk, Spock and McCoy had been thrown in the brig, but a jailbreak by Scotty temporarily frees them.

Sybok confronts the Star Trek trinity, and makes one last attempt to convert them. His technique involves revealing the sources of an individual's deepest pain. He tries this on McCoy and Spock, but even after they re-experience the most painful moments of their past, they remain loyal to Kirk, who refuses Sybok's intervention. But the Enterprise penetrates the Great Barrier that guards the center of the galaxy, and is approaching Sha Ka Ree.

Sybok, Kirk, Spock and McCoy beam to the surface, where they encounter the massive visage and booming voice of a being who first claims to be the God of many planets' prophesies. But when he inquires how they got there, and asks them to bring their starship closer, Kirk impudently inquires, "What does God need with a starship?" The answer is a searing bolt of ire to the chest. God is revealed to be a prisoner on this planet, with the implication that this is a criminal imposter.

Sybok realizes his error and arrogance and sacrifices himself to give the others time to escape. Spock and McCoy are beamed to the Enterprise, but Kirk is left to deal with the non-god's wrath. A subplot involving a pursuing Klingon ship pays off in Kirk's rescue. The last scene repeats the situation of one of the first: Kirk, Spock and McCoy are back around a campfire at Yosemite National Park, singing "Row, row, row your boat" to the accompaniment of Spock's Vulcan lute.