Gensei Kaitō Den is set in the same world as Gensei Kitan. Important characters from Gensei Kitan (including its protagonist, the dog Smash) appear in the game, and some of them are playable. However, the main hero is a young and very ambitious thief named Ali-Baba - who is, naturally, the leader of a band of 40 robbers. The game is divided into chapters; each one describes an episode from Ali-Baba's "career", from train robbery to treasure hunt and even discovery of the magic lamp.