Understanding why related species combine calls in different ways could provide insight into the selection pressures on the evolution of combinatorial communication. African savannah elephants (Loxodonta africana), African forest elephants (Loxodonta cyclotis), and Asian elephants (Elephas maximus) all combine broadband calls (roars, barks, and cries) and low-frequency calls (rumbles) into single utterances known as “combination calls.” We investigated whether the structure of such calls differs among species and whether any differences are better explained by phylogenetic relationships or by socio-ecological factors. Here, we demonstrate for the first time that the species differ significantly in the frequency with which they produce different call combinations using data from multiple study sites. E. maximus and L. africana mostly produced roar-rumble combinations, while L. cyclotis produced a more even distribution of roar-rumble, rumble-roar and rumble-roar-rumble combinations. There were also significant differences in favored structure among populations of the same species. Moreover, certain call orders were disproportionately likely to be given in particular behavioral contexts. In L. africana, rumble-roar-rumble combinations were significantly more likely than expected by chance to be produced by individuals separated from the group. In E. maximus, there was a marginally non-significant trend for rumble-roar-rumbles to be given more often than expected by chance in response to a disturbance. Site-specific socio-ecological conditions appear more influential for call combination structure than phylogenetic history.