Syntax allows human beings to build an infinite number of sentences from a finite number of words. How this unique, productive power of human language unfolds over the course of language development is still hotly debated. When they listen to sentences comprising newly-learned words, do children generalize from their knowledge of the legal combinations of word categories or do they instead rely on strings of words stored in memory to detect syntactic errors? Using novel words taught in the lab, we recorded Evoked Response Potentials (ERPs) in two-year-olds and adults listening to grammatical and ungrammatical sentences containing syntactic contexts that had not been used during training. In toddlers, the ungrammatical use of words, even when they have been just learned, induced an early left anterior negativity (surfacing 100–400 ms after target word onset) followed by a late posterior positivity (surfacing 700–900 ms after target word onset) that was not observed in grammatical sentences. This late effect was remarkably similar to the P600 displayed by adults, suggesting that toddlers and adults perform similar syntactic computations. Our results thus show that toddlers build on-line expectations regarding the syntactic category of upcoming words in a sentence.