Click languages, the languages of southern Africa that utilize clicks and tsks to in their words, have the most phonemes of any language; and among them, !Xoo has the most, an astonishing 130-164 phonemes depending on which !Xoo dialect and on how you define phonemic sounds. By contrast, the dialect of English with the most has 44, and Hawaiian and Rotokas have 11. But most of these sounds are clicks, which are unusual to begin with, and when you discount clicks, then languages like !Xoo go way down.
So what is the language with the most sounds when you don't count clicks? West !Xoo, for example, drops from 164 to ~49 (again, there is disagreement about how to count the phonemes here), which is a very manageable size and close to English. In order to find the language with the most phonemes, we must leave the hot sands of Africa's deserts for the cold but verdant mountains of the Caucasus.
In some of the villages of the Russian Caucasus, we find the Northwest Caucasian languages, tongues that have survived the rise and fall of dozens of mighty empires and thousands of kings. All of the languages boast enormous consonant inventories and surprisingly tiny vocalic inventories. As far as I know, none of them have more than three vowels and most have two. On the other hand, the number of consonants is quite high.
Ubykh, a Northwest Caucasian language that went extinct in 1992, had the most phonemes of any language of all time (again, discounting clicks). It had 84 consonants and two vowels (a third, /u/, appeared in loanwords). Its last speaker, Tevfik Esenc, passed away at age 88 in Turkey. Together with the linguist Georges Dumezil, he recorded hundreds of hours of Ubykh speech. The wealth of recordings has helped us greatly understand the nature of Ubykh and Northwest Caucasian languages in general. Here is Esenc reading the Ubykh story "Eating fish makes you clever," in his native tongue. Subtitles in French.