When immersed in a new environment we are challenged to decipher initially incomprehensible streams of sensory information. Yet, quite rapidly, the brain finds structure and meaning in these incoming signals, helping us to predict and prepare ourselves for future actions. This skill relies on extracting the statistics of event streams in the environment that contain regularities of variable complexity: from simple repetitive patterns to complex probabilistic combinations. Here, we test the brain mechanisms that mediate our ability to adapt to the environment's statistics and predict upcoming events. By combining behavioral training and multi-session fMRI in human participants (male and female), we track the cortico-striatal mechanisms that mediate learning of temporal sequences as they change in structure complexity. We show that learning of predictive structures relates to individual decision strategy; that is, selecting the most probable outcome in a given context (maximizing) vs. matching the exact sequence statistics. These strategies engage distinct human brain regions: maximizing engages dorsolateral prefrontal, cingulate, sensory-motor regions and basal ganglia (dorsal caudate, putamen), while matching engages occipito-temporal regions (including the hippocampus) and basal ganglia (ventral caudate). Our findings provide evidence for distinct cortico-striatal mechanisms that facilitate our ability to extract behaviorally-relevant statistics to make predictions.SIGNIFICANCE STATEMENTMaking predictions about future events relies on interpreting streams of information that may initially appear incomprehensible. Past work has studied how humans identify repetitive patterns and associative pairings. However, the natural environment contains regularities that vary in complexity: from simple repetition to complex probabilistic combinations. Here, we combine behavior and multi-session fMRI to track the brain mechanisms that mediate our ability to adapt to changes in the environment's statistics. We provide evidence for an alternate route for learning complex temporal statistics: extracting the most probable outcome in a given context is implemented by interactions between executive and motor cortico-striatal mechanisms compared to visual cortico-striatal circuits (including hippocampal cortex) that support learning of the exact temporal statistics.