Natural pedagogy emerges early in development, but "good" teaching requires tailoring evidence to learners' knowledge. How does the ability to reason about others' minds support early pedagogical evidence selection abilities? In 3 experiments (N = 205), we investigated preschool-aged children's ability to consider others' knowledge when selecting evidence in the service of teaching. Results from Experiment 1 revealed that 4-year-olds reliably selected evidence to rectify others' false beliefs, and provided causal explanations in their teaching, whereas 3-year-olds did not. In Experiment 2, we tie children's evidence selection abilities to theory of mind (ToM) development, above and beyond effects of age and numerical conservation abilities. In Experiment 3, we employed a 6-week training of children's pedagogical evidence selection with a new teaching task, and further explored the relationship between these skills and children's ToM abilities. We qualitatively replicated our results from Experiment 2 and report tentative evidence for a link between the pedagogical training and improvements in ToM. Together, our findings suggest important connections between reasoning about others' minds and evidential reasoning in natural pedagogy during early childhood.