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. In this study, we investigate whether both types of dependencies can be learned together, similarly to the task facing young children. Statistical learning of adjacent dependencies (probability = .17) and non-adjacent dependencies (probability = 1.0) was assessed in two experiments using a modified serial-reaction-time task. The results showed (i) increasing online sensitivity to both dependency types during training, (ii) better nonadjacency than adjacency learning, and (iii) nonadjacency learning being highly correlated with adjacency learning, suggesting that adjacency and non-adjacency learning can occur in parallel and might be subserved by a common statistical learning mechanism. An overnight break between two training sessions helped the online learning performance of slower learners to approach that of faster learners, but the same amount of training without such a break (a 15-min interval) did not, suggesting that memory consolidation may play a role in statistical learning of complex statistical patterns, especially for slower learners.