Few mammalian species produce vocalizations that are as richly structured as bird songs, and this greatly restricts the capacity for information transfer. Syntactically complex mammalian vocalizations have been previously studied only in primates, cetaceans and bats. We provide evidence of complex syntactic vocalizations in a small social mammal: the rock hyrax (Procavia capensis: Hyracoidea). We adopted three algorithms, commonly used in genetic sequence analysis and information theory, to examine the order of syllables in hyrax calls. Syntactic dialects exist, and the syntax of hyrax calls is significantly different between different regions in Israel. Call syntax difference is positively correlated to geographical distance over short distances. No correlation is found over long distances, which may reflect limited dispersal movement. These findings indicate that rich syntactic structure is more common in the vocalizations of mammalian taxa than previously thought and suggest the possibility of vocal production learning in the hyrax.