Many grammatical dependencies in natural language involve elements that are not adjacent, such as between the subject and verb in "the dog always barks". We recently showed that non-adjacent dependencies are easily learnable without pauses in the signal when speech is presented rapidly. In this study, we used an online measure to look at the relationship between online parsing and the learning performance from the offline assessment of non-adjacent dependency learning. We found that participants who showed current parsing of the language online also learned the dependencies better. However, this pattern disappeared when they are explicitly told where the boundaries are before parsing. Theories of non-adjacent dependency learning are discussed.