A barren underground wasteland, Gehenna is an area filled to the brim with teeth, eyes, veins, and other organic materials. Also in the stage is a large pool of blood in the background. The columns, statues, and other broken debris in the stage seem to imply that an old civilization used to live in the area. A glimmer of light shines the reddish area from above. Double has described the place as her domain.
Gehenna appears in Eliza's story, following Double's surprise attack against her. Using her blood manipulation, Eliza creates a path from Final Atrium to Gehenna for herself and her servants, enabling her to absorb the blood within the place and fight Double on even grounds.
The stage also appears in Beowulf's story mode when Double loses her Zane disguise and devours Beowulf for straying from her plans when he wants to defeat the Skullgirl Marie. After seeing that she captured several other people, including those he previously fought, Beowulf faces the monstrous creature and subdues her momentarily before Annie comes to rescue everyone from her evil clutches.
- Gehenna is named after a place outside ancient Jerusalem where the worshippers of Baal had child sacrifices and was described as "filled with the blood of innocents".
- Gehenna is the only stage that does not show up in the random stage rotation.