Problem solving is central to game-based learning research. In this study, middle grade students achieved significant learning gains from gameplay interactions that required solving a science mystery based on microbiology content. Student trace data results indicated that effective exploration and navigation of the hypothesis space within a problem-solving task was predictive of student learning and in-game performance. Students who selected a higher proportion of inappropriate hypotheses demonstrated smaller learning gains and completed fewer in-game goals. Although there was no relationship observed between providing correct explanations for hypothesis selections and learning gains, students providing incorrect explanations completed fewer goals within the game. Finally, there was no significant gender effect observed on the relationship between hypothesis testing strategies and learning or in-game performance. Hypothesis testing strategies play a central role in narrative-centered learning environments, demonstrating their connections to learning gains and problem solving in gameplay.