 In the year 2304, Earth is under attack. The armies of Mars, led by the Regulator and his top aid Jens Maul, want to invade the Blue Planet. Queen Metapha and her council are out of options, the entire space fleet has been wiped out already. The entire fleet minus one ship, to be exact: The "Surprise" has traveled that far off course that nobody actually misses it and its - er - lukewarm crew. While Earth is fighting for mere survival, Captain Kork, chief engineer Schrotty and the Vulcanette first officer Mr. Spuck prepare for the annual Miss Waikiki contest aboard the ship, somewhere at the end of the universe. They are summoned to Earth by fax, but a marten damage prevents flight with pug speed, low batteries prevent beaming at business class, and economy is definitely not an option. Help is on its way in the form of Taxi pilot Rock, who takes Kork, Spuck and Schrotty to Earth HQ, where he promptly falls in love with Queen Metapha, and since his ride got shot from the sky, the government owes him money anyway. Now, a desperate plan is set in motion: The Surprise crew is to time-travel into the year 2004, where a crashing UFO brought all the new engineering knowledge to Earth, and thus made it possible to colonize Mars in the first place. With a swiss army laser, the UFO is to be destroyed and so the future to be changed. But Jens Maul and his army already come crashing through the doors, and in the chaos, Kork, Spuck, Queen Metapha and Rock manage to flee to the past, but unfortunately end up in 14th century, medieval Europe. Also, Jens Maul gets a hold of the time machine s manual and follows their track through the ages. During the time jumps, the Surprise s time travelers face new (and old) bad guys in every place they go, with Jens Maul closely at their heels. To him, the whole Mars existence is at stake, and he s quite motivated to kill for it, whereas Korks and Spucks main concern is to be back in time for the Miss Waikiki beach contest.