The ability to interpret and reason from Tree of Life (ToL) diagrams has become a vital component of science literacy in the 21st century. This article reports on the effectiveness of a research-based curriculum, including an instructional booklet, laboratory, and lectures, to teach the fundamentals of such tree thinking in an introductory biology class for science majors. We present the results of a study involving 117 undergraduates who received either our new research-based tree-thinking curriculum or business-as-usual instruction. We found greater gains in tree-thinking abilities for the experimental instruction group than for the business-as-usual group, as measured by performance on our novel assessment instrument. This was a medium size effect. These gains were observed on an unannounced test that was administered ~5-6 weeks after the primary instruction in tree thinking. The nature of students' postinstruction difficulties with tree thinking suggests that the critical underlying concept for acquiring expert-level competence in this area is understanding that any specific phylogenetic tree is a subset of the complete, unimaginably large ToL.