Narrative as a game design feature constantly yields mixed results for learning in the literature. The purpose of this exploratory mixed-methods case study was to examine design heuristics and implications governing the role of narratives in a digital game-based learning (DGBL) environment for math problem solving. We collected data via observation, semi-structured interviewing, and video recording with twenty-seven college students with diverse demographic backgrounds. Video logging resulted in 2276 behavioral events for quantitative analysis. The study indicated: (1) 11 narrative-governed actions for game-based math problem solving; (2) the positive correlations between narrative usage and successful game-based math problem solving; and (3) the gender effects: girls are supported by game narratives designed with intrinsic integration (i.e., object-oriented narrative) for math problem solving more than boys. The study findings highlighted the critical role of game narratives in a sandbox DGBL environment for math problem solving as well as gender-inclusive design of narratives. A set of data-driven design heuristics and implications for the game narrative in DGBL were delineated and suggested.