In 1975 Gene Roddenberry began developing a Star Trek movie for Paramount Pictures. He wrote a script called Star Trek: The God Thing, which would've seen the crew of the Enterprise sent to face God, who was threatening mankind. Unsurprisingly Paramount weren't keen on the story but asked Roddenberry to stay on and oversee the movie and take submissions from other writers.
A budget of $7.5million was set for the film, Francis Ford Coppola, Steven Spielberg, George Lucas and Robert Wise were all approached and asked to direct what would've been the first Star Trek movie. All four directors declined, they were either busy on other projects or thought the budget too low. Philip Kaufman was then approached, Roddenberry himself didn't think that Kaufman would agree so was surprised when he did.
Of all the story ideas that were submitted one called Planet of the Titans stood out to the production team, so the British writing duo of Chris Bryant and Allan Scott were officially hired in October 1976 to complete the screenplay.
At this time though negotiations with William Shatner were not going well and so their first draft did not feature Captain Kirk. Shatner eventually signed a new contract and was added to the movie, but then Leonard Nimoy dropped out of the project due to his likeness being used in a commercial without his permission. Paramount finally managed to resolve the issue and the crew of the Enterprise were all on board.
In Bryant and Scott's completed screenplay of Planet of the Titans the Enterprise was sent to respond to a distress signal from the USS DaVinci. Upon arrival there is no sign of the other Starship, however Captain Kirk is struck by electromagnetic waves and starts to behave erratically. He commandeers a shuttle craft and heads off in to space and vanishes without a trace. Spock orders the Enterprise home, resigns from Starfleet and heads to Vulcan to purge himself of his human half.
Three years later, the newly refitted Enterprise, complete with a new crew commanded by Captain Gregory Westlake, is ordered to the location where Kirk disappeared. On the way they pick up Spock, and upon arrival discover a planet that appears to be the mythical Planet of the Titans, the home of a lost race with super technology. The Klingons had been searching for this planet too, and it is thought that whoever rescues the Titans will control the destiny of the Universe. But it is soon discoverd that the planet is about to be destroyed by a black hole, and the Enterprise is likely to be dragged along with it as the ship is trapped by the force field surrounding the planet.
The Enterprise saucer separates from the rest of the ship and crash lands on the planet. Spock finds Kirk, who has been living there in the wild along with the other trapped beings. The duo discover that the rulers of this world are not the Titans, but a race called the Cygnans who had wiped the Titans out.
Spock, Kirk and the rest of the landing party attempt to leave the planet in the saucer section, but as they reattach to the Enterprise the Cygnans transport themselves on board. Realising that he must save the Federation from this highly dangerous race Kirk maneuvers the Enterprise straight into the black hole. The Cygnans are destroyed and the Enterprise emerges from the black hole finding itself in orbit around prehistoric Earth. The crew teach early man how to make fire, in effect becoming the Titans themselves.
The finished script was submitted in March 1977, the following month Paramount rejected it and the writers quit, however Philip Kaufman decided to undertake a massive rewrite in an attempt to keep the project alive. He later explained;
"My version was really built around Leonard Nimoy as Spock and Toshiro Mifune as his Klingon nemesis. My idea was to make it less “cult-ish”, and more of an adult movie, dealing with sexuality and wonders rather than oddness; a big science fiction movie, filled with all kinds of questions, particularly about the nature of Spock’s [duality]—exploring his humanity and what humanness was. To have Spock and Mifune’s character tripping out in outer space. I’m sure the fans would have been upset, but I felt it could really open up a new type of science fiction."It was a very different idea for a Star Trek movie, and one that seemed just too much for Paramount. In May 1977, just as Star Wars was about to arrive in cinemas, Paramount pulled the plug on the project.
Some concept art had been completed along with some models of the new ships, some of which would go on to appear in Star Trek: The Next Generation. Kaufmann went on to direct Invasion of the Body Snatchers, and Paramount decided that maybe Star Trek did not belong on the big screen, maybe the crew of the Enterprise should undertake a new five year mission. A project called Star Trek: Phase II began, and you can read about that here.