I might break this down into multiple posts, just for ease of reading and writing.
So, discussion of a Star Trek movie began very early - in 1967, as a possible production while the show was on hiatus between the second and third series. DeForrest Kelly was privy to these discussions, and sarcastically said that nobody would be interested in a movie based on a TV series.
By the mid-70s, the idea of a Trek movie had been floated a few times. Dorothy Fontana wrote a letter to a Trek fanzine in 1972, talking about the volume of fan mail that Paramount recieved about the show even then, and that it was leading to the notion of a movie as a putative pilot for a sequel series. While no movie manifests at this time, it is the impetus to the creation of the animated series.
In 1973, Gene Roddenberry first approached Paramount to pitch a movie based on an unused episode idea from the original Star Trek pitch document. Paramount are willing to have Roddenberry write the script, but not act as producer (both because of his rep from Star Trek, and his perceived failure as a producer on Pretty Maids All in a Row). Roddenberry counters by demanding a then-unprecedented $100,000 fee to write the movie, and the deal falls through. Sensing the rise of SF as a popular movie genre, Paramount does decide to set up two subsidiary effects studios the following year. A leadership change in 1975 will lead to an attempt to shut one of them down, which will have repercussions for TMP
In 1974, independent of Roddenberry's attempts, Paramount's head of finance begins to lobby for a Trek movie, citing the financial success of the TV show in syndication. Roddenberry is approached by Paramount's new head in October of that year to produce a movie, but he holds out until the following March to accept the offer.
By January 1976, the project is switched from a movie to a TV series, with script requests sent out to various TV and SF writers including Robert Silverberg, Harlan Ellison, Ray Bradbury and Theodore Sturgeon. Michael Eisner, then the head of Paramount's TV department rejects all the story proposals, and the project becomes a movie again. At this point, the project gets a name: Star Trek: Planet of the Titans. A sprawling story in which Kirk commands a redesigned Enterprise in a race against the Klingons to discover a mythical race of aliens called the Titans, only to be sent back in time to become the Titans themselves, giving primitive man the gift of fire. The script is rejected, as is a rewrite, and the project goes back to TV!
So, by June 1977 - a month after Star Wars is released, the TV show has a name - Star Trek Phase II, and Roddenberry has been working on a writer's bible alongside some of the show's contracted writers and editors. Paramount are planning a TV network, and intend Phase II to be a cornerstone show (where have we heard that one before?)
The pre-production period for Phase II is wrought with conflict and stress. Roddenberry plays power games, most notably with Harold Livingston (a studio hire intended to be the creative producer), which continues for two years and delays the show's production. By July 1977, plans for the Paramount network are scrapped, but with $500,000 already spent on the various movie and TV reboot attempts, and a number of pay or play contracts signed with cast members, Paramount decide not to scrap Phase II, instead turning it into a TV movie and a possible pilot. "In Thy Image", a script by Alan Dean Foster is selected for the production. The production budget is now $8 million.
In October, Gene Roddenberry sent out details to many Trek fan clubs, confirming that William Shatner had agreed to return to the show, but Leonard Nimoy had not, citing being unwilling to undertake the rigours of a TV schedule as well (in reality, he was also holding out while Paramount refused to compensate him for usage of his likeness on merchandise, a long standing clash). As a result, Spock's role on the ship would be replaced with two new characters - a Vulcan science officer named Xon, and first officer Will Decker. Peresis Khambatta is cast as Ilia a week after this missive goes out. Within 4 weeks, Phase II's budget is upped to $15 million.
The following month, after Close Encounters of the Third Kind is a huge hit, there's a feeling that Paramount has missed a big chance by faffing about so much with Phase II. Production of Phase II is suspended to determine the possibility of upgrading to a cinema release.
Over Christmas 1977/New Year 1978 the name Star Trek Phase II is officially dropped in favour of Star Trek: The Motion Picture. Production issues would continue to plague the movie, but I think this post has gone on long enough, so I'll be back in a while to talk about the actual work on the movie itself...