Targeted as a highly desired skill for contemporary work and life, 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 science problem-solving task was predictive of student science content learning and in-game performance. Students who selected a higher proportion of appropriate hypotheses demonstrated greater learning gains and completed more in-game goals. Students providing correct explanations for hypothesis selection completed more in-game goals; however, providing the correct explanation for hypothesis selection did not account for greater learning gains. From the analysis, we concluded that hypothesis testing strategies play a central role in game-based learning environments that involve problem-solving tasks, thereby demonstrating strong connections to science content learning and in-game performance. (Contains 2 tables and 2 figures.)