Recent advances in single-cell genomics are propelling a flurry of discoveries about the cellular composition of the brain and other organs across species. These discoveries, coupled with experimental manipulations, have begun to reveal how variation between species in the proportion of cell types, including the outright disappearance of some cell types and the emergence of new ones, contributes to the evolution of behavior. This review highlights these emerging findings in the context of more traditional approaches to study the evolution of behavior and discusses important outstanding questions in this field.