In order to become proficient native speakers, children have to learn the morpho-syntactic relations between distant elements in a sentence, so-called non-adjacent dependencies (NADs). Previous research suggests that NAD learning in children comprises different developmental stages, where until 2 years of age children are able to learn NADs associatively under passive listening conditions, while starting around the age of 3–4 years children fail to learn NADs during passive listening. To test whether the transition between these developmental stages occurs gradually, we tested children’s NAD learning in a foreign language using event-related potentials (ERPs). We found ERP evidence of NAD learning across the ages of 1, 2 and 3 years. The amplitude of the ERP effect indexing NAD learning, however, decreased with age. These findings might indicate a gradual transition in children’s ability to learn NADs associatively. Cognitively, this transition might be driven by children’s increasing knowledge of their native language, hindering NAD learning in novel contexts. Neuroanatomically, maturation of the prefrontal cortex might play a crucial role, promoting top-down learning, affecting bottom-up, associative learning. In sum, our study suggests that NAD learning under passive listening conditions undergoes a gradual transition between different developmental stages during early childhood.