lo Rodis, who had worked on two previous Star Trek features, was appointed the role of art director, and worked with Shatner to establish the film's visual design. Shatner sought a grittier and more realistic feel to the Star Trek universe, and so the two worked together to visualize the film from start to finish. After Shatner explained the entire story in a day-long session, Rodis went home and sketched out each scene from the script. Shatner was pleased with the results, especially with Rodis' designs for Shatner's most expansive or dramatic shots.
Rodis's input in developing the early character and costume designs was significant. Shatner praised his costume designs as being futuristic but plausible and in keeping with the continuity established in previous Star Trek films. After being disappointed by the costume designers approached to realize Rodis' ideas, Shatner suggested that Rodis become the costume designer as well. Bennett hired Dodie Shepard as the costume supervisor; Shepard's role was to oversee the costume fabrication and keep track of the clothes during filming. To save on costs, Shepard clothed extras with existing items from Western Costume's warehouses. The constrained budget meant Shatner could not completely redesign the Starfleet uniforms, but Rodis created new brown field uniforms for the film's location scenes as well as the leisure clothes the crew wears during shore leave.
Rodis and Shatner also drew up sketches of what the various aliens seen in the film would look like. Shatner picked Kenny Myers as the special-effects makeup artist. Myers discussed the sketches with Shatner and made casts of actors' faces using dental alginate. These casts were used for close-up, high-quality "A" makeups, as well as less complicated masks for far-away and background characters. Shatner hired Richard Snellas makeup supervisor, advising him to make each Klingon forehead distinct.
Shatner hired Herman Zimmerman as production designer. His decision was based on Zimmerman's work on the sets for Star Trek: The Next Generation, and he felt that the designer could convey Shatner's futuristic yet grounded aesthetic. Zimmerman was immediately put in charge of designing all-new sets for the Klingon Bird of Prey bridge, the Enterprise's bridge, elevator shafts and bowels, and Nimbus III interiors. At one point, he was building five sets at once. Art department head Michael Okuda created LCARSbacklit controls on the Klingon ship and Enterprise. The corridors for the Enterprise were the same as those used in the Next Generation television series. The bridge set alone cost $250,000. The Nimbus III city of Paradise was one of the last locations to be designed and created, because its design relied on what exterior location and terrain was used. Zimmerman created a sketch of the town's layout over three days, drawing inspiration from a circular Moroccan fortress. Creation of the city cost $500,000 and took five weeks of construction in 100 °F (38 °C) heat.
Tim Downs scouted possible areas for location filming. He looked for a location that could stand in for three different venues without the production having to move or change hotels: the film's opening scene; the God planet's establishing shots; and the Nimbus III Paradise City. Downs was familiar with the Mojave desert and thought that locations near Ridgecrest, California, would serve the production's needs, so he took photos based on sketches Rodis had provided of what the locations might look like. Downs also shot photos with filters and tried to accomplish dust effects with his car to replicate ideas for how some sequences would be shot. When Downs returned with the photos, Shatner felt that the locations the scout found would be perfect for the film.