When children learn their native language, they have to deal with a confusing array of dependencies between various elements in an utterance. Some of these dependencies may be adjacent to one another whereas others can be separated by considerable intervening material. Research on statistical learning has begun to explore how such adjacent and non-adjacent dependencies may be learned—but in separate studies. In this paper, we investigate whether both types of dependencies can be learned together, similarly to the task facing young children. Statistical learning of adjacent and non-adjacent dependencies was assessed using a modified serial-reaction-time task. The results showed (i) increasing online sensitivity to both dependency types during training, and (ii) non-adjacent dependency learning being highly correlated with adjacent dependency learning. These results suggest that adjacency and non-adjacency learning can occur in parallel and that they might be subserved by a common statistical learning mechanism.