Physical interactive environments can come in many forms: museum installations, amusement parks, experimental theaters, and more. Programming these environments has historically been done by adults, and children, as the visiting participants, have been offered few pre-created choices to explore. Given these creative limitations, the goal of our research has been to develop programming tools for physical interactive environments that are appropriate for use by young children (ages 4-6). We have explored numerous design approaches over the past two years. Recently we began focusing on a “physical programming” approach and developed a wizard-of-oz prototype for young children. This paper presents the motivation for this research, the evolution of our programming approach, and our recent explorations with children.