Brood-site mutualisms represent extreme levels of reciprocal specialization between plants and insect pollinators, raising questions about whether these mutualisms are mediated by volatile signals and whether these signals and insect responses to them covary geographically in a manner expected from coevolution. Cycads are an ancient plant lineage in which almost all extant species are pollinated through brood-site mutualisms with insects. We investigated whether volatile emissions and insect olfactory responses are matched across the distribution range of the African cycad Encephalartos villosus. This cycad species is pollinated by the same beetle species across its distribution, but cone volatile emissions are dominated by alkenes in northern populations, and by monoterpenes and a pyrazine compound in southern populations. In reciprocal choice experiments, insects chose the scent of cones from the local region over that of cones from the other region. Antennae of beetles from northern populations responded mainly to alkenes, while those of beetles from southern populations responded mainly to pyrazine. In bioassay experiments, beetles were most strongly attracted to alkenes in northern populations and to the pyrazine compound in southern populations. Geographical matching of cone volatiles and pollinator olfactory preference is consistent with coevolution in this specialized mutualism.