The story begins with two young men in an underground shelter playing a video game called Devil Busters, which retells the opening events of Digital Devil Story: Megami Tensei. After being the game's boss, they release the demon Pazuzu, who claims that the two men are the Messiahs destined to be the saviors of mankind. He grants the Hero the ability to summon and talk to demons, and his friend the gift of magic. Pazuzu gives them the mission of destroying the demon lords that have taken control of Tokyo, starting with Bael, the demon that sealed him inside Devil Busters. The heroes venture outside the shelter, and they are recognized as messiahs by the Church of Messiah. Upon reaching Tokyo Tower, however, the heroes find a witch who was also named a messiah by Pazuzu, but claims he has been manipulating them for his own gain. The friend refuses to believe that Pazuzu is using them. In order to progress in the story, the player has to side with the witch, causing the friend to leave and become his enemy.