It was just an ordinary cruise ship gig for the four musicians. The band leader, known only as the Flute (the player names him and the other heroes before the game begins), never thought that it will end in such a way... Suddenly, a tornado engulfed the ship, and the poor musician found himself in the magical world populated by angelic creatures and monsters! Naturally, this world, called Astralius by its inhabitants, needs salvation. Only the Magic Flute can avert a demonic threat. Apparently, our hero is the only flutist in all the dimensions, since it is now his task to take the unlikely role of a noble paladin, find other musicians to help him on his quest, and show everyone that music can, indeed, save the world!

Despite the somewhat unusual choice of protagonists, Mateki Densetsu Astralius is quite an "old-school" Japanese-style RPG. The player controls the nameless flutist and other musicians (trumpet player, drummer, etc.), who later join the party, exploring the top-down world, visiting towns to buy weapons, armor, and items, descending into dungeons, automatically leveling up, progressing the story in a linear fashion, and fighting randomly appearing enemies in turn-based combat viewed from first-person perspective. Casting magic spells is called "performing" in the game, though it requires magic points, like in other games of this kind. Those magic points must be bought in special shops.

Unlike most other PC Engine (TurboGrafx) CD RPGs, there are no voice overs or animated cut scenes in this game.