The game opens with the young girl dragging an oversized attaché case toward a warehouse with difficulty. "Bloody" Harry Macdowell has just carried out a coup against Big Daddy, the leader of the Millennion organization, and his daughter Mika needs to find someone that can protect her and stop Harry's mad plans. The occupants of this warehouse include a kindly looking old doctor, and a man with a notable scar on his face. Mika arrives, and the man with the scar claims the contents of the case: two massive handguns. That man is revealed to be the game's title character Grave, and now that he is armed he can start his mission. Gungrave first approaches its stages as a series of missions issued by Dr. T, first to gather information on the current makeup of Millennion from a low-level street gang, and next destroying a research facility that creates Harry's undead soldiers. In the third stage, while attempting to pump information from an informant, Grave comes into contact with the leadership of the Millenion organization—once friends and allies that he now faces as enemies. Each have used the research Harry supported to give themselves inhuman powers. From here on, Grave is hounded by each member as he makes his way to Harry's tower at the heart of the city.