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.