Young infants are very sensitive to feature distribution information in the environment. However, existing work suggests that they do not make use of correlation information to form certain perceptual categories until at least 7 months of age. We suggest that the failure to use correlation information is a by-product of familiarization procedures that encourage infants to over encode individual exemplars rather than relations across exemplars. By changing the exemplar presentation regime to one in which exemplars are rapidly (2s durations) and repeatedly presented we find that 4-month-olds can form perceptual categories on the basis of feature correlation information. In addition, this ability emerges rapidly between 114 and 134 days. We argue that the ability to process correlation information is present very early on but that the demonstration of that ability in categorization tasks is mediated by the demands of the task the infant is tested with. Copyright (c) 2005 John Wiley & Sons, Ltd.