A key promise of narrative-centered learning environments is the ability to make learning engaging. However, there is concern that learning and engagement may be at odds in these game-based learning environments. This view suggests that, on the one hand, students interacting with a game-based learning environment may be engaged but unlikely to learn, while on the other hand, traditional learning technologies may promote deep learning but provide limited engagement. This paper presents findings from a study with human participants that challenges the view that engagement and learning need be opposed. A study was conducted with 153 middle school students interacting with a narrative-centered learning environment. Rather than finding an oppositional relationship between learning and engagement, the study found a strong positive relationship between learning outcomes, in-game problem solving and increased engagement. Furthermore, the relationship between learning outcomes and engagement held even when controlling for students' background knowledge and game-playing experience. Additional analyses revealed that males tended to report significantly greater presence in the virtual environment than girls, and students with more game-playing experience reported significantly greater presence in the virtual environment than students with minimal game-playing experience. Follow up analyses suggested that differences in presence may be more strongly associated with game-playing experience than gender. (Contains 4 tables and 5 figures.)