The game takes place at an unknown point of time after the original film. An extraterrestrial bounty hunter kidnaps Lilo and brings her aboard the spaceship laboratory of a robotic, mosquito-like alien named Dr. Pestus, who plans to use her as food for his genetically-modified mosquito army. Stitch must go out into space to rescue Lilo and defeat Dr. Pestus.

In most levels, the player takes control of a four-armed, plasma blaster-wielding Stitch who must run and gun his way past enemies and various other obstacles to complete the level. In puzzle-platform-styled levels, the player takes control of Lilo as she sneaks around the spaceship to find a way to escape and contact Stitch. In tube shooter-styled segments, Stitch must fly a spaceship to reach the next level, shooting down other enemy ships and dodging obstacles along the way.