The gameplay is similar to Tetris, but here the player has to direct blocks of stone and treasure to create closures, which then eliminates the treasure and adds to the player's score. Also, if a full line of stone blocks is formed, they will disappear in a similar fashion to Tetris, and also add to the player's score. The game's name comes from its mascot, which is a super deformed version of the ancient Egyptian queen Cleopatra. Additionally, the game utilizes an Egyptian theme.
Following the initial arcade release, a PlayStation version and a Sega Saturn version were released in Japan, followed later on by the Dreamcast version in 2001. A PlayStation version was released in the USA & Europe in 2003, with the original arcade game being released in the Taito Legends 2 compilation title. An arcade only sequel called Cleopatra Fortune Plus was released later in 2001, on the Sega NAOMI system. Both the Dreamcast port and this new sequel were created in association with Altron instead of Natsume.