Originellement, les ennemis de l'équipage de l'Entreprise devaient être des Romulans, mais le studio Paramount pencha cependant pour des Klingons, plus connus du grand public. Problème, le vaisseau des méchants originels, les Romulans, avait déjà été construit. Heureusement, la série télévisée avait déjà expliqué au fans que les technologies de deux peuples étaient très semblables.
Star Trek 3 est le premier long métrage réalisé par Leonard Nimoy, connu dans le monde entier pour son rôle de Monsieur Spock. L'acteur avait déjà dirigé quelques épisodes de séries telles que Mission : impossible ou T.J. Hooker. Son apparition derrière la caméra est le fruit d'un échange entre la société de production Paramount et le comédien, qui n'a accepté de voir son personnage réapparaître que s'il pouvait réaliser lui-même le film.
La production de Star Trek 3 a été perturbée par un important incendie qui s'est déclenché à l'intérieur des studios Paramount en 1983. Selon les témoins, le comédien William Shatner (Amiral Kirk) aurait aidé plusieurs victimes avant l'arrivée des secours.
Des séquences entières de Star Trek 2: la colère de Khan, tourné deux ans auparavant, ont été réutilisées dans Star Trek 3, ceci afin de rappeler le destin de Monsieur Spock, disparu à la fin de l'épisode précédent.
L'existence même de l'Atlantide restant à prouver, il a fallu imaginer une nouvelle langue de A à Z pour les besoins du film. Une tâche confiée au linguiste Marc Okrand, créateur de la langue vulcain dans Star Trek 2: la colère de Khan et de celle des Klingons dans Star Trek 3: A la recherche de Spok. Fidèle à la théorie de l'Atlantide comme source de toute civilisation et aux prémisses du film situés en Islande, Marc Okrand s'est basé sur les langues indo-européennes pour fabriquer un alphabet de 29 lettres et de 10 allant de 0 à 9.
La "voix" de l'ordinateur de bord de l'USS Execelsior n'est autre que celle de Leonard Nimoy, trafiquée pour l'occasion.