Numerous empirical studies have provided evidence of the effectiveness of an explicit and reflective approach to the learning of issues associated with the nature of science (NOS) (c.f. Abd-El-Khalick and Lederman in "J Res Sci Teach" 37(10):1057-1095, 2000). This essay reports the results of a mixed-methods association study involving 130 preservice teachers during the course of a three class unit based upon the history of science using such an approach. Within the unit the phenomenon of industrial melanism was presented as a puzzle for students to solve. Students were explicitly asked to reflect upon several NOS issues as they developed and tested their own explanations for the "mystery phenomenon". NOS views of all participants were characterized by means of surveys and follow-up interviews with a subsample of 17 participants, using a modified version of the VNOS protocol (c.f. Lederman et al. in "J Res Sci Teach" 39(6):497-521, 2002). An analysis of the survey results informed by the interview data suggests NOS views became more sophisticated for some issues, e.g., whether scientific knowledge requires experimentation; but not others, e.g., why scientists experiment. An examination of the interview data informed by our experiences with the unit provides insight into why the unit may have been more effective with regard to some issues than others. This includes evidence that greater sophistication of some NOS issues was fostered by the use of multiple, contextualized examples. The essay concludes with a discussion of limitations, pedagogical implications, and avenues for further research.