Several, related hypotheses on the origins of primates attribute their derived morphological traits (e.g. grasping limbs, orbital convergence, reduced olfactory apparatus, and enlarged cranium) as adaptations to the behavioral demands of arboreal ecologies such as angiosperm terminal branch feeding or acrobatic grasp-leap locomotion. Arboreal habitats are also suggested to have selected for sensory shifts from close-range olfaction to longer-distance auditory based communication and, in some cases, sophisticated acoustic signals. We merge and extend these classic theories by hypothesizing that song-like acoustic displays evolved as signals of 'dimensional precision' in sensory-motor tasks required for locomotion via aerial trajectories through complex canopy habitats. To test this hypothesis we compiled spectrographic vocal repertoires and behavioral data from field studies of 51 species (representing all primate families) and performed phylogenetically controlled regression analyses. Here we report significant correlated evolution [PGLM, p < 0.001] between vocal-unit clustering (a measure of song complexity) and prevalence of aerial locomotion (leaping and suspensory arm swinging). Other factors such as mating system and diet showed less strong associations with complex calls while arboreality and climbing alone were non-significant. Our analysis suggests that primate songs could serve as honest signaling mechanisms in species that frequently traverse via aerially discontinuous paths through gapped canopy habitats.