Riportare in giro per lo spazio l'Enterprise fu, nel 1979, un'impresa non da poco, segnata da un'infinita serie di indecisioni (la più macroscopica delle quali fu il dubbio se farne una seconda serie TV o un film per le sale), difficoltà nel convincere il cast originale (Leonard Nimoy non ne voleva sapere), avere una sceneggiatura decente (le riprese iniziarono che un copione definitivo ancora non c'era), effetti speciali di alcune sequenze non finiti (Vulcano all'inizio) o addirittura mai realizzati per mancanza di tempo (come il V'ger finalmente in orbita attorno alla Terra, ad esempio). Il tutto giunse comunque nelle sale americane nel Dicembre '79 grazie alla dedizione di un organizzatore instancabile come Jeffrey Katzenberg, a quei tempi ai vertici della Paramount e oggi al fianco di Spielberg e Geffen al timone della Dreamworks SKG, ed un regista di solidissima esperienza come Robert Wise (Ultimatum alla Terra, Andromeda), che per la prima volta nella sua carriera fu costretto a far si che un suo film uscisse senza neanche aver il tempo di rivederne il montaggio e fare proiezioni test: solo nel 2001, grazie alla riedizione in DVD, è riuscito ad apportare al film le modifiche che, avendone avuto il tempo, avrebbe fatto allora.

Il successo del film comunque dette il via libera ad un secondo cine-capitolo della saga per cui la macchina produttiva si mise immediatamente all'opera per tornare la, dove nessun umano era mai giunto prima. Subentrarono due nuovi produttori, Robert Sallin e Harve Bennett, e Gene Roddenberry fu relegato al ruolo più marginale di Consulente Esecutivo. Nimoy ancora una volta non ne voleva sapere di rimettersi le orecchie a punta e fu convinto ad apparire solo a patto che Spock morisse. Tutti concordavano che il primo film era troppo lungo e aveva abbondanti pause nella narrazione a malapena sorrette dalla bellezza dei sontuosi effetti speciali. Bennett ebbe l'idea di riportare in azione il personaggio di Khan, apparso in un episodio della serie originale (Spazio profondo, Tit. Orig.: Space seed) e interpretato da un attore navigato come Ricardo Montalban. "Penso che quell'episodio fosse splendido." ricorda Bennett "Montalban poi è un attore di stampo classico, capace di recitare le sue battute con grande forza. Fornisce poi al personaggio una sorta di arroganza macho che ti fa credere che sia davvero geneticamente modificato, un uomo più forte, più intelligente, superiore. Un eroe è niente senza un nemico. Se sopraffai uno smidollato non hai fatto granché, ma se sopraffai uno come Khan sei davvero la definizione di eroe." Dal canto suo l'attore, impegnato in Fantasy Island, volle rivedere molte volte l'episodio della serie classica, per riscoprire le radici su come aveva interpretato il personaggio anni prima.

Da un soggettino preliminare di una pagina, che fu pronto già nel Dicembre 1980, si arrivò successivamente ad avere una stesura firmata da Bennett e Jack B. Sowards che si intitolava Star Trek - The Omega Syndrome, che prevedeva un interludio sentimentale tra Kirk e una del personale di bordo, la morte di Spock quasi all'inizio del film, ed un confronto faccia a faccia tra Kirk e Khan con tanto di uso di poteri mentali acquisiti dai sopravvissuti delle guerre eugeniche. Il Sistema Omega della storia era una tecnologia che avrebbe permesso a Khan di diventare super potente e dominare intere razze, oltre naturalmente a cercare la sua vendetta nei confronti di Kirk. Una versione successiva dello script introduceva il concetto del Progetto Genesi, avvicinandosi a quello che poi sarebbe stato il copione definitivo. Il titolo era infatti Star Trek - The Genesis Project. Per sviluppare ulteriormente il soggetto Bennett si rivolse a Samuel Peeples, autore del secondo pilota originale, quel Where no one has gone before che fece accettare l'idea della serie classica agli executives della TV. A parere di Peeples ci si sarebbe dovuti distaccare maggiormente dai temi e modi della serie classica. "Star Trek" spiega "era un'audace e innovativa creazione di Roddenberry; è diventata una leggenda, base per un fenomeno di culto tra gente giovane e molto intelligente. Sfortunatamente è diventato anche una specie di scherzo tra persone altrettanto intelligenti delle nuove generazioni. (...) Per quelli di noi, come Gene ed io, che sono stati coinvolti in Star Trek sin dal suo concepimento è fin troppo facile essere influenzati dalla tradizione che si è creata. Ma, proprio per la natura stessa dell'idea originale, tradizione, deja vu e nostalgia non possono essere di primaria influenza nei nuovi Star Trek. Il buon senso dice che è giusto usare i concetti base che si sono rivelati così giusti, ma lo stesso buon senso dice di non essere troppo nervosi e di aprire le nostre menti ad una creatività più aperta, del tipo che fu alla base stessa della nascita della serie." Peeples produsse un soggetto intitolato Star Trek - Worlds that never were nel quale "la missione dell'umanità nel futuro non può essere una di conquista e distruzione. Ad ogni tipo e forma di vita deve essere data l'opportunità di potersi evolvere ai massimi livelli e perché questo possa avvenire occorrono controlli ambientali e cambiamenti. Questo è lo scopo e la vera forza motrice alla base dell'Operazione Genesis: la creazione da mondi sterili di ambienti adatti all'evoluzione di miriadi di forme di vita." Curiosamente in questa versione di Star Trek II, forse proprio per allontanarsi dai collegamenti a suo avviso troppo stretti con la vecchia serie TV, Peeples non includeva il personaggio di Khan. C'erano invece molti altri elementi di trama già presenti nel lavoro di Sowards, più un paio di alieni provenienti da un'altra dimensione e che cercavano di usare i loro poteri per poter comandare nella nostra.