Infants learn to map words onto situations, even though there is a bewildering array of potential referents for each word in their environment. Previous studies of cross-situational learning have shown that learning correspondences between words and referents is possible, when all words refer to objects. However, in child-directed speech, the infants primary input is more complex as it comprises multi-word utterances from different grammatical categories, some of which do not form word-object pairings. In study 1, we confirmed in corpus analyses of child-directed speech that utterances typically contain words from several different grammatical categories. In study 2 we confirmed that participants could still learn from cross-situational statistics when (1) the language also incorporated words that did not refer to objects, and (2) when the language additionally contained function words that marked the referring and non-referring words. Cross-situational learning is robust to grammatical categories in acquiring word-object pairings.