In 3008, the crew of the Intergalactic Space Police cruiser Infinity is on patrol duty in deep space. The ship is captained by the incompetent Cornelius Butt and his crewmen: his first officer, Sgt. Thor ; pilot "space-cowboy" Pvt. Robert "Buzz" McHenry ; Maurice, a black humanoid alien with pointy ears and bat wings; and Sam, an Asian man who quotes Confucius. Also aboard is Galaxina, a voluptuous blonde android servant, and Rock-Eater, a rock-eating alien prisoner confined to the brig. While the Infinity hides behind an asteroid, a suspicious-looking, bird-like ship flies by, and Buzz decides to pursue it. They try to question the ship's pilot, a mysterious masked figure who rudely terminates communications. The two ships exchange laser fire, but the bird-ship gets away. After the encounter, Galaxina serves a dinner of chicken-flavored food pills to Captain Butt, Thor, and Buzz. The three men are stunned by her beauty, and Thor receives an electric shock when he slaps her buttocks. Tired of the pill-food, Captain Butt decides to eat an alien egg confiscated from the rock eater prisoner. The egg sickens him, and, on top of the dinner table mimicking the scene from the movie "Alien," he coughs up a baby alien creature that quickly scurries away. Later, the crew receive orders to proceed to the prison planet Altair One to recover a priceless stolen gemstone called the Blue Star; every time the stone is mentioned, an invisible heavenly chorus is heard by the characters. The trip will take the Infinity 27 years to complete, requiring that the crew enter cryogenic sleep. Before doing so, they make a quick stop at an asteroid brothel. Galaxina remains in charge of the ship while the crew is in stasis. While alone, she reprograms herself to become more human. She learns to talk and disables her electrical defense mechanism. She visits Thor's sleep chamber periodically, embracing it and telling the sleeping Thor that she loves him. Later, the baby alien visits Butt's chamber and tampers with the controls. When the crew awakens at their destination, Butt emerges from his pod an old man with shaggy gray hair. Thor is seduced by Galaxina and he falls in love with her. Although she lacks the proper hardware to have sex, she assures Thor that these components can be ordered from the android catalog. Thor can only fantasize about Galaxina until they return home and get her modifications. The ship reaches Altair One and lands. Knowing that the local aliens are hostile to humans, Galaxina volunteers to go look for the Blue Star while the others stay on the ship. She walks into town and enters a "human restaurant," and discovers that this means the restaurant serves humans as food to alien creatures. There, she finds Ordric, the masked figure the crew encountered earlier. Ordric possesses the Blue Star and Galaxina attacks him. Galaxina discovers Ordric is a robot when she smashes his head open. Ordric is deactivated and Galaxina takes the Star. As she flees the town, she is captured by a gang of bikers, descendants of the first settlers of Altair One. Their leader announces that he will sacrifice Galaxina to their deity, "Harley-David-Son", and with the power of the Blue Star he will take control of the universe. Thor and Buzz, who have been looking for Galaxina, rescue her from the bikers and return to the ship. Ordric attacks and boards the Infinity as soon as they reach space. He takes back the Blue Star and confines everyone in the brig. The baby alien, now fully grown, sneaks onto the bridge and attacks Ordric. The creature, believing Butt to be its mother, goes to the brig and gives Butt the keys to the cell door. The crew escapes the brig and rushes the bridge, finding that Ordric has been torn to pieces. While contemplating the reward they will receive for returning the Blue Star, they notice that Rock-Eater has eaten it.
Originally, the film was supposed to be shot in 20 days. Due to unforeseen bad weather, some sets could not be used and so the production lost a few days of filming. As a result, the producers demanded that scenes be cut to keep the shoot on schedule. Because these scenes are missing from the final film, director William Sachs calls the final cut "too slow paced", as he would have edited it in a faster style had he been able to include the scenes that were never filmed.
