The following year, pre-production began again on a film with a treatment called Planet of the Titans and subsequent script produced by British writers Chris Bryant and Allan Scott with the intention of keeping costs down by filming in the United Kingdom. There were difficulties in ensuring that both William Shatner and Leonard Nimoy were signed to the film as Shatner's deal with Paramount had expired and Nimoy was concerned with unauthorized merchandising. Philip Kaufman was signed up to direct, after several others were asked first. The plot would have seen the crew investigating the homeworld of the mythical Titans, and in escaping through a black hole are hurled into the prehistoric past where they teach early man how to make fire.
After their script was rejected, Bryant and Scott quit, and Kaufman created a new script treatment, but it too was rejected, and the project was killed on May 8, 1977, some two weeks before the release of Star Wars. Various reasons have been cited for the cancellation, including regime change at Paramount, and that executives thought they had missed their window due to Star Wars' imminent release, believing science fiction fans would not pay to see two such films. Paramount immediately changed course and launched a plan to take Star Trek back to television via a new TV network as Star Trek: Phase II.
Following the cancellation of Star Trek: The Original Series on NBC in 1969, there were several attempts, influenced by the success of the series in broadcast syndication and from the attendance of fans at conventions, to transfer the series into a film. By March 1972, Roddenberry said that there was interest in a Star Trek feature film and that there was even potential for returning the series to NBC.
In May 1975, Roddenberry entered into a development deal with Paramount Pictures to develop a film based on Star Trek. Principal photography was intended to start on July 15, 1976, but was later pushed back to 1977. It was given the initial title of Star Trek: The God Thing and had a budget of $5 million. Roddenberry's plot would have reunited the crew of the Enterprise and sent to face God, who was threatening earth. Paramount Studios Chief executive officer Barry Diller ended the development deal in August 1975, although Roddenberry was allowed to keep his office at the studio. Roddenberry pursued the project and invited several others to submit story and script ideas, including his personal assistant Jon Povill, as well as writers Robert Silverberg, John D. F. Black and Harlan Ellison. Ellison's treatment featured the crew forced to travel back in time to prevent a reptilian race from wiping out humanity at the "dawn of time". He met with Paramount executives, including Barry Trabulus, who recently read Chariots of the Gods? by Erich von Däniken (1968) and wanted the Maya civilization to be featured in the film. Ellison and Trabulus disagreed, and Ellison left the meeting refusing to have anything more to do with the film. George Lucas later enquired about whether or not Star Trek was available for purchase in order to be turned into a film, and went on to create Star Wars instead.
In the original treatment by Chris Bryant and Allan Scott, the USS Enterprise investigates the disappearance of the USS DaVinci. Upon arriving at the last known location, they find no other ship, but Captain James T. Kirk is struck by electromagnetic waves and leaves the Enterprise in a shuttlecraft. He pilots it out into space and disappears. Three years pass and the Enterprise returns to the area under Captain Gregory Westlake, after picking up Spock, who had retired from Starfleet and returned to Vulcan. The crew discovers a previously hidden planet at the location where Kirk vanished. They believe it to be the planet of the Titans, a mythical and powerful alien race. However, the planet is being drawn into a black hole. The Klingons also want to claim the planet. Spock travels to the surface and finds Kirk, who has been living on the planet for three years. Together, they discover the planet is inhabited by the Cygnans, who destroyed the Titans. The planet and the Enterprise enter the black hole, with the Cygnans being destroyed in the process. The ship emerges in orbit of Earth during the Paleolithic era, and the crew teach early man to make fire, in effect playing the role of Prometheus the Titan themselves, similar to the alien influence on human ancestors in 2001: A Space Odyssey (1968). Planet of the Titans also explored the concept of the third eye, and was later compared to the appearance of the Greek Gods in the original series episode "Who Mourns for Adonais?".
After Bryant and Scott departed the project, director Philip Kaufman tried to re-write the story, with the resulting treatment heavily inspired by Olaf Stapledon's books Last and First Men and Star Maker. He later described this version as being "less 'cult-ish' and more of an adult movie, dealing with sexuality and wonders rather than oddness". He intended this version to feature Spock facing off against a Klingon nemesis, A role for whom Kaufman wanted Japanese actor Toshiro Mifune. Kaufman explained that it would have featured the two undergoing a psychedelic experience and summed it up by saying that "I'm sure the fans would have been upset, but I felt it could really open up a new type of science fiction." While Povill had felt that Bryant and Scott's treatment was unsuccessful, he thought that Kaufman's was worse.
Planet of the Titans was expected to be filmed in the United Kingdom in order to keep production costs low. In July 1976, Jerry Isenberg was assigned to be executive producer of the new film and British writers Bryant and Scott were hired in September. The duo had no science fiction writing experience, but had written the films Don't Look Now (1973) and Joseph Andrews (1977). Roddenberry defended the hiring of the pair, saying "I'm very excited about some of the ideas they've come up with. The concept that only a science fiction writer can write science fiction motion pictures is ridiculous. Look at me. I came up with Star Trek, and I was a dramatic writer. I wrote for TV." Bryant believed he earned the screenwriting assignment because his view of Kirk resembled what Roddenberry modeled him on; "one of Horatio Nelson's captains in the South Pacific, six months away from home and three months away by communication". Their 20-page treatment was submitted the following month. It was entitled Planet of the Titans and was received favourably by Diller and fellow executive Michael Eisner. The writers were told by Paramount to proceed to script on October 6.
Jon Povill wrote up a list of possible directors for the project, which included Francis Ford Coppola, Steven Spielberg, Lucas and Robert Wise, but all were busy at the time or unwilling to work with a $7.5 million budget. Although his agent did not expect him to do it, Philip Kaufman signed on to direct. Roddenberry introduced him to the series by showing him ten episodes, including those he felt were the most representative and popular of the series: "The City on the Edge of Forever", "The Devil in the Dark", "Amok Time", "Journey to Babel", "Shore Leave", "The Trouble with Tribbles", "The Enemy Within", "The Corbomite Maneuver", "This Side of Paradise" and "A Piece of the Action". On signing, Kaufman was pleased to direct Star Trek. He discussed it with Lucas, and said that he "felt he could go through the roof". NASA employee Jesco von Puttkamer was hired as an advisor on the film.
There were issues with casting the film. Paramount Studios' deal with William Shatner had ended and so the first draft of the film did not feature Captain Kirk. He was later added as a new contract was signed. However, Leonard Nimoy dropped out of the film because he was concerned over potential merchandising after his likeness as Spock was used in a Heineken advertisement without either his permission or an arrangement for royalties. He had refused to speak publicly about the issue, but Shatner explained it in an interview. The situation was eventually resolved and Nimoy signed on to appear in Planet of the Titans.
Early work was promising and by the fall of 1976 the project was building momentum. Fans organized a mail campaign that flooded the White House with 400,000 letters, influencing President Gerald Ford to rechristen the Space Shuttle Constitution to Enterprise. Bryant and Scott's proposal became the first accepted by the studio in October; Roddenberry immediately stopped work on other projects to refocus on Star Trek, and the screenwriters and producers were swamped with grateful fan mail. By the start of 1977 the project's official title was changed to Star Trek—The Motion Picture (a title reapplied to the eventually released 1979 film). The elation was short-lived; the first draft of the completed script was not finished until March 1, 1977, and pressure was mounting for Paramount to either begin production or cut its losses and cancel the project. Producer Jerry Isenberg began scouting filming locations and hired designers and illustrators to complement the script.
Ken Adam, an Academy Award-winning production designer, was hired to design the film. Adam did a number of concept renderings of various settings, including a geometric chamber where Spock would have a vision of his own death, a giant crystalline "space brain", various Enterprise interiors, including a hangar deck and an "open" saucer interior with tubes connecting various platforms–a design concept he later executed for the space station interior in the James Bond film Moonraker. He also sketched exterior configurations for the starship which was to be refitted after nearly being destroyed by a black hole in the opening scenes.
Adam then hired conceptual designer Ralph McQuarrie, who had recently worked on designs for Star Wars. McQuarrie worked with Adam in London for six weeks doing various "blue sky" concepts because "there was no script". McQuarrie's renderings of the Enterprise have been compared to those for the Star Wars Star Destroyer, but much of the design can be traced to Adam's sketches. His concepts include images of the Enterprise saucer module separated from the rest of the vessel, an element which had been mentioned in The Original Series but never seen on screen. Other McQuarrie works included various interiors and exteriors of the Enterprise, shuttlecraft concepts, planetary landing facilities, and an inhabited asteroid featuring a space dock. McQuarrie later went on to work on designs for Star Trek IV: The Voyage Home.
Crude study models of at least two of the Enterprise concepts were constructed, and these were utilized as background elements in shots of later productions, including in the spacedock in Star Trek III: The Search for Spock, as a shipwreck in the Star Trek: The Next Generation episode "The Best of Both Worlds", and as part of a reserve fleet in The Next Generation episode "Unification". One of these Enterprise concepts would later be the basis for the USS Discovery, the Star Trek: Discovery television series. Show runner Bryan Fuller confirmed that it was the basis of the new ship initially, but added that it was "to a point that we can’t legally comment on it until [our legal team] figures out some things".
Bryant and Scott turned in their script on March 1, 1977. It was rejected by Paramount and they departed the project in April 1977 because they found that Kaufman's and Roddenberry's ideas for the film repeatedly conflicted. They later said they were disappointed as they felt it had been "absolutely a 'go' picture" and that "It was just one of those deals that happens at studios from time to time that fell down the middle." Jeffrey Katzenberg informed the director on May 8 that the film was cancelled; it had an increased budget of $10 million at the time. This was some three weeks prior to the release of Star Wars. Several explanations for the cancellation have been put forth. One claims the studio felt that the production had taken too long and another science fiction film would not be successful so soon after Star Wars because the fans would not pay to see two science fiction films. Kaufmann later claimed that Paramount had attributed the cancellation to the success of Star Wars at the box office, but as Titans was cancelled prior to Star Wars release the box office could not have played a factor. Diller stated that it was cancelled because both treatments felt forced and different from the episodes of The Original Series. He instead suggested that they returned to the series format and therefore moved forward with a project that would become the never-completed Star Trek: Phase II TV series Kaufmann went on to direct films such as Invasion of the Body Snatchers (1978) and The Right Stuff (1983). Although the film was never made, it was later discussed by critics and writers. David Hughes included it in his 2008 book The Greatest Science Fiction Movies Never Made in the chapter about the planned Star Trek films of the 1970s. In a list of ten unmade "Awesome-Sounding" Star Trek projects on the website WhatCulture! in 2013, Xavier Santana included Planet of the Titans at number ten.