After the original "Star Trek" TV series proved a success in syndication, Paramount became interested in making a "Star Trek" movie. Writers who contributed ideas or draft scripts in 1975-77 included Gene Roddenberry, Jon Povill, Robert Silverberg, John D F Black, Harlan Ellison, Theodore Sturgeon, and Ray Bradbury. A story called "Star Trek: Planet of Titans" was selected; Chris Bryant and Allan Scott wrote a script, which was then rewritten by Philip Kaufman. At this point Star Wars (1977) burst upon the world, and Paramount reacted by canceling "Star Trek: Planet of Titans" before pre-production started. Allegedly they thought there wasn't a sufficient market for another big science-fiction film.
Paramount then announced that they would be creating a new TV network, initially operating one night a week showing Paramount TV-movies and a new "Star Trek" series about the Enterprise's second 5-year mission, with most of the original cast and the title "Star Trek Phase II". It soon became clear that they could not make a go of the new network, but Paramount continued work on the new series in the hope of selling it to one of the existing networks.
For a previous unproduced TV series of his called "Genesis II", Gene Roddenberry had created a story he called "Robot's Return". This was now rewritten for "Star Trek" by Alan Dean Foster under the title "In Thy Image", and proposed as the 2-hour premiere episode of "Star Trek Phase II". However, Paramount executive Michael Eisner responded, "We've been looking for the feature for five years and this is it", and made the final decision to forget the new series and produce the story as a movie.
The decision was made in August 1977, but in order to keep the team together during the necessary renegotiation of contracts, Paramount kept it secret until March 1978; when Rona Barrett broke the secret in December 1977, they denied it. Meanwhile, they pretended that the TV series was still going to happen, even soliciting scripts for episodes that would never be made. Sets built for the TV series were used in the movie, but modelwork had to be redone after the changeover was made public, due to the need for finer detailing in a movie.
TV director Robert Collins was hired to direct the 2-hour premiere, but after the change to a movie, Paramount wanted a more experienced director and replaced him with Robert Wise.
Gene Roddenberry wanted Alan Dean Foster to write the final script for the film, but Harold Livingston thought him too inexperienced and tried to hire Steven Bochco, who was unavailable; Michael Cimino, who wasn't interested; and William Norton, who initially accepted but found it beyond his capabilities. In the end Livingston did the job himself. He disagreed repeatedly with Roddenberry over rewrites and other matters, and quit and returned several times.
The TV series was to have three new regular characters. Paramount was concerned that William Shatner might ask for too much money to continue playing Kirk if the run of the series was extended beyond the initial order of 13 episodes; the character of Decker was created so that if Kirk had to be written out, Decker could become the series' new lead role. Decker was played in the movie by Stephen Collins.
Leonard Nimoy declined to return as Spock for the series, so a new Vulcan character "Xon" was created to be the new science officer. An employee of an agent was dating a young actor, David Gautreaux, who had no agent of his own; she suggested him for the part and he got it, then was told that it was actually for a movie. When Nimoy finally agreed to do the movie, Spock replaced Xon in the script and Gautreaux was given the smaller part of Commander Branch.
The character of Lieutenant Ilia, played by Persis Khambatta, was also intended as a continuing role in the TV series.
The original version of the "Space Walk" sequence had both Spock and Captain Kirk traveling through V'ger. Because it complicated the flow of the film, the scene was reshot with Spock alone, and that's what's seen in the final cut. However, a fraction of this alternate scene remains in the longer version, where Kirk says, "I have him in sight".
The V'ger prop was so large and involved so much work that one end of it was being used in scenes while the other end was still being built.
When Spock travels through V'ger and sees all the incredible imagery, Darth Vader and Miss Piggy can be seen. It comes right after his line "Who or what are we dealing with?".
In the scene where Kirk addresses the crew prior to launching, much of the crew were extras who were noted Star Trek fans, including Bjo Trimble, co-organizer of the letter-writing campaign that kept the original "Star Trek" alive for a third season.
In the novelization of this film, the identity of the other person killed in the transporter accident is revealed: it is Lori Ciana, Admiral Kirk's wife. Since the novelization was written by Gene Roddenberry himself, it can be considered an official part of the Trek canon.
It was understood in the script, but not in the movie, that Commander Will Decker was the son of Commodore Matthew Decker, the half-crazed starship captain who committed suicide in the "Star Trek" television episode "The Doomsday Machine."