Anxiety disorders are prevalent and significantly impact young children and their families. One hypothesized risk factor for anxiety is heightened responses to sensory input. Few studies have explored this hypothesis prospectively. This study had two goals: (1) examine whether sensory over-responsivity is predictive of the development of anxiety in a large prospective sample of children, and (2) identify whether anxiety mediates the relationship between sensory over-responsivity and behavioral challenges. Children’s sensory and anxiety symptoms were assessed in a community sample of 917 at 2–5 and again in 191 of these children at 6 years old. Parents also reported on a number of additional behavioral challenges previously found to be associated with both sensory over-responsivity and anxiety separately: irritability, food selectivity, sleep problems, and gastrointestinal problems. Forty three percent of preschool children with sensory over-responsivity also had a concurrent impairing anxiety disorder. Preschool sensory over-responsivity symptoms significantly and positively predicted anxiety symptoms at age six. This relationship was both specific and unidirectional. Finally, school-age anxiety symptoms mediated the relationship between preschool sensory over-responsivity symptoms and both irritability and sleep problems at school-age. These results suggest sensory over-responsivity is a risk factor for anxiety disorders. Furthermore, children who have symptoms of sensory over-responsivity as preschoolers have higher levels of anxiety symptoms at school-age, which in turn is associated with increased levels of school-age behavioral challenges.