Originating on the arcades (where it was known as Demon's World to the Western audience), Horror Story is an "old-style" side-scrolling platformer/shooter. The basic gameplay premise is very simple: shoot and jump your way through large amounts of monsters, defeat the boss, proceed to the next level. There is no narrative of any kind in the game, and no cut scenes; the hero is a tough-looking Duke Nukem-look-alike equipped with guns.

The screen is scrolling at all times, even if the player character doesn't move. The levels are almost entirely linear, the only choice sometimes being to stay on the ground or jump to the higher platforms. Cooperative two-player mode is available.

Though shooting is decidedly the main gameplay element here, jumping (particularly double-jumping) must be used liberally to navigate the hero through platform-based stages, and avoid and kill enemies (since jumping on their heads eliminates them as well). Weapons can be switched by catching power-ups, which appear as floating, constantly changing letters. Depending on the letter the player decides to take, the hero will get different weapons. These weapons include: a steady energy beam of moderate power; flamethrower; bombs; a short-distance grenade launcher of sorts; and a gun that spits fireballs in three different directions.

As the name implies, the game has a horror theme. The game begins in what looks like old Japan, complete with traditional Japanese demons, but later switches to more "mainstream" horror, complete with haunted towns, ghosts, zombies, skeletons, etc.