Extracting the statistics of event streams in natural environments is critical for interpreting current events and predicting future ones. The brain is known to rapidly find structure and meaning in unfamiliar streams of sensory experience, often by mere exposure to the environment (i.e., without explicit feedback). Yet, we know little about the brain pathways that support this type of statistical learning. Here, we test whether changes in white-matter (WM) connectivity due to training relate to our ability to extract temporal regularities. By combining behavioral training and diffusion tensor imaging (DTI), we demonstrate that humans adapt to the environment's statistics as they change over time from simple repetition to probabilistic combinations. In particular, we show that learning relates to the decision strategy that individuals adopt when extracting temporal statistics. We next test for learning-dependent changes in WM connectivity and ask whether they relate to individual variability in decision strategy. Our DTI results provide evidence for dissociable WM pathways that relate to individual strategy: extracting the exact sequence statistics (i.e., matching) relates to connectivity changes between caudate and hippocampus, while selecting the most probable outcomes in a given context (i.e., maximizing) relates to connectivity changes between prefrontal, cingulate and basal ganglia (caudate, putamen) regions. Thus, our findings provide evidence for distinct cortico-striatal circuits that show learning-dependent changes of WM connectivity and support individual ability to learn behaviorally-relevant statistics.