Which natural languages have the fewest phonemes?
Central Rotokas (https://en.wikipedia.org/wiki/Rotokas). It has five vowels (/a i u e o/) and three consonants (/p t k/), for a total of 8 phonemes.
Let's assume we count a phoneme as 1 sound and its allophones, and don't count tone and length differences as different phonemes. Then Rotokas (https://en.wikipedia.org/wiki/Rotokas_language) has 6 consonants and 5 vowels, for 11 total. Pirahã (https://en.wikipedia.org/wiki/Pirah%C3%A3_language#Phonology) has 10-12, depending on the source, under that definition. A commoner definition of phoneme would be a sound and its allophones, believing the ability to distinguish vowels with length and tone. That gives Pirahã 13-16 and Rotokas 14-16 A stingy definition, counting all occasional separate sounds, would give Pirahã 16 and Rotokas 19. Note: Hawaiian and other Polynesian languages often have limited inventories. For Hawai'ian, the common (middle) definition would give them 18 phonemes. Note: Conlangs, of course, have even fewer phonemes in some cases.
Keep in mind that tonal languages may have a relatively small number of phonemes, but that number is multiplied by a number of pitches or contours. Chinese languages/dialects are a prime example. [I should say: a relatively small number of vowels and consonants or other vocalizations, not a small number of phonemes.]
Another candidate is Silbo Gomero, depending on what you mean by "language" and "phoneme". SG, used on La Gomera in the Canary Islands, is a mode of producing Gomera Spanish, which converts the output of the phonology of Gomera Spanish and implements it physically via whistling. There are 6 distinct whistle-patterns implementing the segments coming out of the phonology (this does result in neutralization, where /d,r,l,n,j/ map to the same output).