The dorsal striatum is important for highly specialized functions including movement, learning, and habit formation. However, it is not known if species-specialized behaviors are associated with cellular specializations in the striatum. Here, we compared single-nucleus RNA sequencing (snRNA-seq) data from human, chimpanzee, rhesus macaque, common marmoset, and pale spear-nosed bat caudate (CN) and putamen (Pu) separately as well as mouse caudoputamen (C-Pu), which represents divergence among species spanning approximately 94 million years of evolution. We observed a lower neuron-to-glia ratio in primate striata compared to non-primates, reflecting the allometric scaling of neuron density and relative glia density invariance in larger brains. Among neurons, eccentric spiny projection neurons (eSPNs) - an SPN of unknown function - showed significantly lower proportions in non-primate striata for both CN and Pu. Focusing on the heterogeneity within interneurons, we identified two bat striatal interneuron cell types that are nearly absent in other species: which express LMO3, and co-express FOXP2 and TSHZ2. Other striatal interneurons also showed significantly differential abundance between primates and non-primates. In summary, we provide a comprehensive snRNA-seq dataset of dorsal striatum, identify novel interneuron innovations in bat, and uncover fundamental cellular composition differences between primate and non-primate striata.