This paper describes the design, evaluation, and lessons learned from a project involving the implementation of an immersive virtual environment for children called NICE (Narrative-based, Immersive, Constructionist / Collaborative Environments). The goal of the NICE project was to construct a testbed for the exploration of virtual reality as a learning medium within the context of the primary educational reform themes of the past three decades. With a focus on informal education and domains with social content, NICE embraces the constructivist approach to learning, collaboration, and narrative development, and is designed to utilize the strengths of virtual reality: a combination of immersion, telepresence, immediate visual feedback, and interactivity. Based on our experiences with a broad range of users, the paper discusses both the successes and limitations of NICE, and concludes with recommendations for research directons in the application of immersive VR technologies to children's learning.