In human languages, different speech sounds can be contextual variants of a single phoneme, called allophones. Learning which sounds are allophones is an integral part of the acquisition of phonemes. Whether given sounds are separate phonemes or allophones in a listener's language affects speech perception. Listeners tend to be less sensitive to acoustic differences between sounds that are allophones. This study investigated the mechanisms behind the learning of allophones by looking at adults' sensitivity to acoustic differences between two unfamiliar sounds when they were exposed to input in which the sounds behave like separate phonemes versus allophones in terms of their contextual distribution. The results of two experiments showed that adults became less sensitive to acoustic differences between two unfamiliar sounds after being exposed to input in which the sounds were in complementary distribution and that the emergence of allophonic perception was constrained by the phonetic naturalness of complementary distribution.