In revenge for being banished, Satan and his demons invaded Heaven. Although the forces were immortal, the demons used a different tactic - they would transform the angels into various monsters, shadows of their former selves. An angel named Tamagon went to God, and was instructed to defeat the Devil and reverse the curse. Tamagon travelled through a portal to Hell, where he ended up in the Devil's Labyrinth.
Just like the original Demon World for NES, Tamagon must grab crosses to eat the Boa Boa dots. Eating all of them clears the level. However, whenever Tamagon comes in contact with an enemy while holding a cross, he is engaged in an RPG-style battle. Each type of enemy has a different statistics value. Tamagon has three options in battle - CLAW, FIRE BREATH, and RUN.
CLAW is a melee attack, where Tamagon attacks with his claw. This does little damage, but does not use up any of Tamagon's BBP (Boa Boa points). FIRE BREATH has Tamagon breath fire. Although it does more damage than Claw, it uses up a BBP. RUN attempts to leave the battle, however, any enemy that you run from becomes upgraded. Each Boa Boa dot eaten is worth one BBP.
As in the NES version, levels in Demon World DS alternate between two goals - collect all the dots, and seal the enemy generator. There's also bonus levels, but these are only accessible by finding Bonus Keys. A Bonus Key is hidden in each level, but it is well-hidden. There's also Trophies that can be obtained. Some trophies are hidden in levels. Others are obtained by accomplishments, such as beating a level on one life. There are 100 levels in Demon World DS, each with a different layout. The final level has no maze, just a battle sequence with Satan himself. Once a level is beaten, it can be replayed any number of times.