The ability to recognize individuals based on their vocalizations is common among many species of songbirds. Examining the psychological and neural basis of this functionally relevant behavior can provide insight into the perceptual processing of acoustically complex, real-world, communication signals. In one species of songbird, European starlings (Sturnus vulgaris), males sing long and acoustically complex songs composed of small stereotyped note clusters called motifs. Previous studies demonstrate that starlings are capable of individual vocal recognition, and suggest that vocal recognition results from the association of specific motifs with specific individuals. The present study tests this possibility by examining how variation among the motifs that comprise a song affect its discrimination and classification. Starlings were trained, using operant techniques, to associate multiple songs from a single male starling with one response, and songs from four other male starlings with another response. The level of stimulus control exerted by motif variation was then measured by having subjects classify three sets of novel song bouts in which motifs from the training songs were systematically recombined. The results demonstrate a significant, and approximately linear, relationship between song classification and the relative proportions of familiar motifs from different singers that compose a bout. The results also indicate that the motif proportion effects on song classification are primary to retroactive interference in the recall for specific motifs, and independent of any biases due to the syntactic organization of motifs within a bout. Together, the results of this study suggest that starlings organize the complex vocalizations of conspecifics by memorizing large numbers of unique song components (i.e., motifs) that are then associated with different classes. Because individual starlings tend to possess unique motif repertoires, it is likely that under natural conditions such classes will correspond to individual identity. Thus, it is likely that perceptual processing mechanisms similar to those described by the results of the present study form the basis for individual vocal recognition in starlings.