The game consists of two types of areas: an overhead view where Firebrand traverses the Ghoul Realm, either on the world map or in towns, and individual, side-scrolling, battle levels which feature a boss at the end. In between actual levels, as Firebrand traverses the overhead map of the Ghoul Realm, he is susceptible to random encounters like a typical console RPG. He must defeat the enemies in order to return to the overhead-view map. There are also ghouls that can be encountered that spark a small battle level which the player must defeat in order to get past them.
Firebrand can walk, jump (varying heights depending on items obtained), cling to walls, hover for a period of time (this period is determined by the items the player has obtained), and fire projectiles--the only method of offense in the game. The player starts with one type of projectile; it does not travel very far, and has limited power. Eventually, the player will gain new projectiles, discussed below. Firebrand has a small number of hit points, starting at two and increasing throughout the game based on items or blessings obtained; various enemies and objects drain different amounts of hit points.
As the player progresses, various items are gained which have differing effects. Some items are passive; they increase Firebrand's abilities outright. For example, the Fingernail of the Spectre increases his jumping ability for the remainder of the game, and there are several items that increase the length of time which Firebrand can fly, the final of which allows for him to fly infinitely. There are also items which can be used as needed, such as items to restore health. Additionally, several types of projectiles are obtained throughout the game. All can be offensive tools to defeat enemies, but each has different traits or specialized uses. The Blockbuster, for example, which is the first projectile obtained after Firebrand's starting projectile, is twice as powerful, travels further, and can break special blocks the player may need to pass. Another projectile temporarily creates objects which Firebrand can jump from to reach necessary locations. Projectiles can be selected one-at-a-time from the select menu, as can items such as healing vials. Once located, the Essence of the Soulstream can be used from the menu to fully recover Firebrand's life, but it can only be used once per life or level. It automatically refills after a level, or if a life is lost.
In the final boss battle, the player makes a choice which results in one of two scenarios for how the final battle is played. In one scenario, the player is stripped of all ability-boosting items and powers, leaving him virtually unable to win, and must then fight the final boss. In the other scenario, the player maintains these items and powers, and attempts to win the game.
The story in Gargoyle's Quest takes place several thousand years before the first game.
- Lucifer - the Ghouls 'n Ghosts boss is called Rushifell here.
- Darkoan - the ruler of the Demon Realm.
- Zundo Druer - the first boss of the game, Zundo is a fiery blowfish who emerges from lava in the burning town to attack with living wisps of fire. This can be a tricky fight, since Firebrand can only withstand two hits. After Zundo's defeat, the portal to the Ghoul Realm is opened.
- Four-Eyes - a boss that is really four separate eyeballs that are suctioned on to walls on opposite sides of a room inside a tower. Firebrand must carefully maneuver up and down to each eyeball and shoot at them, all while avoiding the eyeball's projectiles.
- Bellzemos - a large skeletal bee demon that can split into four smaller bee demons. When the smaller bees reassemble, Bellzemos shoots a fireball. When the battle ends, Firebrand is able to free King Darkoan from captivity with the Candle of Poltergeist.
- Zakku Druzer - a boss that appears in the Desert of Destitution. Zakku resembles a giant skeletal snail with two smaller demon heads below his main head; these shoot projectiles at Firebrand. When he is destroyed, Firebrand obtains the Candle of Darkness.
- Breager - known as the King of Destruction, he wants to destroy Makai, after failing to do so on a previous occasion (in the game's prequel). This is his last desperate attempt at doing so. The Destroyers is the name of the army controlled by Breager.
- Mesa Ghoul - hooded, robed figure that is a common enemy in the early part of the game.
- Twin Marr - a merman-like enemy that rises from the water and fires a projectile from its mouth.
- Gorillar - a monster that resembles a cross between a buffalo and a gorilla.
- Bone Snapper - a fish-like enemy.
- Dreadwing - a fly-like enemy that comes in two varieties. Some crawl walls up and down until they spot Firebrand, leaving the wall and flying horizontally, also passing by walls. Others appear flying back and forth between walls, making it difficult for Firebrand to climb or go down areas with them.
- Sand Devil - a demon that only appears in the desert. It rises from the sand and fires a projectile.
Though no in-game credits exist for this game, Harumi Fujita's official worklist states that she is its composer. Yuki Iwai, who composed the prequel as one of her first jobs at Capcom, is often miscredited for having done this title as well.
Yoko Shimomura also lists this title in her worklist as one she provided support on. The extent of her contributions has yet to be determined.