From an evolutionary perspective, we analyze how social complexity affects the complexity of signals. Lemurs offer an excellent example for this research endeavor through their organization into different social systems, ranging from solitary to pair- as well as group-living species. To describe the complexity of signaling systems, we characterize the repertoire of acoustic, visual and olfactory signals, and compare their structure and function, as well as the multimodal use of signals in species, whose social organization differs. In addition, we study how phylogenetic descent shapes the structure of signaling systems and which signals (acoustic, visual or olfactory) are used for species recognition.