The power of human language derives from our ability to generate a huge variety of discriminable vocalizations and map them to a correspondingly huge number of meanings. This ability appears vastly superior to anything known in other animals. As part of the broader goal of understanding what new capabilities were required for language during human evolution, I have investigated the capabilities of nonhuman animals for generating diverse utterances. Two key requirements for open-ended vocal complexity are first the diversity of speech sounds themselves, and second the elaborate, hierarchical manner in which they are recombined into words and phrases. Looking at mammalian vocal production, we find that most species studied thus far appear to vastly underutilize the phonetic potential of their peripheral vocal apparatus. While the descent of the human larynx results in a wider phonetic range in modern humans, recent data show that it is not unique to humans (being found in deer, lions and other species). I argue that this character can be plausibly interpreted as a way of elongating the vocal tract to exaggerate the impression of size conveyed by vocalizations, a phenomenon that might also account for the initial lowering of the larynx in human evolution. This suggests that the descended larynx in humans may have preceded speech considerably, and is not a clear indicator of the possession of language by extinct ancestors. I conclude that the vocal rudiments necessary for a workable speechlike system were already present in ancestral mammals. Turning to the hierarchical organization of sounds into larger wholes, we find a greater gap, but a certain capability for higher-order recombinatory structure is still evident in many vertebrates. However, this ability appears weakly developed in nonhuman primates relative to groups more distantly related to humans (birds, dolphins, whales, etc). Finally I briefly discuss the curious fact that vocal imitation is found, among primates, only in humans. I suggest that our unique linguistic talents rest on a foundation of capabilities shared with other mammals and vertebrates. A deeper appreciation of these shared abilities is necessary for an understanding of what is (or is not) special about humans.