Here we describe a method for teaching the NOS called "Science as Storytelling," which was designed to directly confront narve realist preconceptions about the NOS and replace them with more sophisticated ideas, while retaining a moderate realist perspective. It was also designed to foster a more sophisticated understanding of the science-religion interface, where occasional science-religion conflicts are seen as inevitable in cases where religious beliefs incorporate supernatural intervention in the natural world. We evaluated the program as implemented in a geology course for preservice elementary teachers at Brigham Young University, and showed that it was successful at helping students understand the tentative and creative aspects of scientific thought, and fostering more positive attitudes toward science. Our evaluation also showed that the students adopted a more irenic stance toward science-religion conflict. These results directly contradict fears that emphasizing the creative and tentative aspects of the NOS, and admitting that science and religion sometimes conflict, will cause students to reject scientific claims to an even greater degree.