People assume that objects labelled alike belong to the same category. Here we asked whether the role of labels in categorization depends on individuals' language experience, linguistic abilities, and/or cognitive abilities. We compared monolinguals' and bilinguals' use of phonologically licit words (zeg), illicit words (gsz), and non-linguistic frames (in addition to a baseline condition with no additional cues) in forming novel categories. For both groups, licit words affected categorization more than frames, especially in the absence of perceptual evidence for category boundaries; illicit words also shifted categorization preferences compared to frames. Furthermore, linguistic abilities predicted reliance on both licit and illicit words, and bilingualism predicted reliance on illicit words in categorization. Thus, in both monolinguals and bilinguals, novel (and even unconventional) linguistic labels act as unique category markers but their use in categorization depends on individual language processing skills (and, in some cases, exposure to a second language).