Nearly all theories of language development emphasize the importance of distributional cues for segregating words and phrases into syntactic categories like noun, feminine or verb phrase. However, questions concerning whether such cues can be used to the exclusion of referential cues have been debated. Using the headturn preference procedure, American children aged 1;5 were briefly familiarized with a partial Russian gender paradigm, with a subset of the paradigm members withheld. During test, infants listened on alternate trials to previously withheld grammatical items and ungrammatical items with incorrect gender markings on previously heard stems. Across three experiments, infants discriminated new grammatical from ungrammatical items, but like adults in previous studies, were only able to do so when a subset of familiarization items was double marked for gender category. The results suggest that learners can use distributional cues to category structure, to the exclusion of referential cues, from relatively early in the language learning process.