In language, grammatical dependencies often hold between items that are not immediately adjacent to each other. Acquiring these nonadjacent dependencies is crucial for learning grammar. However, there are potentially infinitely many dependencies in the language input. How does the infant brain solve this computational learning problem? Here, we demonstrate that while rudimentary sensitivity to nonadjacent regularities may be present relatively early, robust and reliable learning can only be achieved when convergent statistical and perceptual, specifically prosodic cues, are both present, helping the infant brain detect the building blocks that form a nonadjacent dependency. This study contributes to our understanding of the neural foundations of rule learning that pave the way for language acquisition.