Brain evolution has primarily been studied at the macroscopic level by comparing the relative size of homologous brain centers between species. How neuronal circuits change at the cellular level over evolutionary time remains largely unanswered. Here, using a phylogenetically informed framework, we compare the olfactory circuits of three closely related Drosophila species that differ in their chemical ecology: the generalists Drosophila melanogaster and Drosophila simulans and Drosophila sechellia that specializes on ripe noni fruit. We examine a central part of the olfactory circuit that, to our knowledge, has not been investigated in these species-the connections between projection neurons and the Kenyon cells of the mushroom body-and identify species-specific connectivity patterns. We found that neurons encoding food odors connect more frequently with Kenyon cells, giving rise to species-specific biases in connectivity. These species-specific connectivity differences reflect two distinct neuronal phenotypes: in the number of projection neurons or in the number of presynaptic boutons formed by individual projection neurons. Finally, behavioral analyses suggest that such increased connectivity enhances learning performance in an associative task. Our study shows how fine-grained aspects of connectivity architecture in an associative brain center can change during evolution to reflect the chemical ecology of a species.