Signal complexity has been linked to social complexity in vocal, but not chemical, communication. To address this gap, we examined the chemical complexity of male and female glandular secretions in eight species of Eulemur. In this diverse clade of macrosmatic primates, species differ by social or mating system and dominance structure. We applied principal component and linear discriminate analyses to data obtained by gas chromatography/mass spectrometry. Beyond the significant effects on chemical signals of gland type, sex, season and species, we found effects of social variables and phylogeny. Notably, female odours were more chemically complex in multimale-multifemale species than pair-bonded species, whereas male odours were more chemically complex in codominant species than female-dominant species. Also, the traditional sexual dimorphism, whereby male signal complexity exceeds that of females, was present in codominant species, but reversed in female-dominant species. Lastly, a positive relationship between the species' pairwise chemical distances and their pairwise phylogenetic distances supported a gradual, but relatively fast mode of signal evolution. We suggest that the comparative method can be a powerful tool in olfactory research, revealing species differences relevant to the understanding of current signal utility and evolutionary processes. In particular, social complexity in lemurs may have selected for olfactory complexity.