Our environments are saturated with learnable information. What determines which of this information is prioritized for limited attentional resources? Although previous studies suggest that learners prefer medium-complexity information, here we argue that what counts as medium should change as someone learns an input's structure. Specifically, we examined the hypothesis that attention is directed toward more complicated structures as learners gain more experience with the environment. College students watched four simultaneous streams of information that varied in complexity. RTs to intermittent search trials (Experiment 1, = 75) and eye tracking (Experiment 2, = 45) indexed where participants attended during the experiment. Using two participant- and trial-specific measures of complexity, we demonstrated that participants attended to increasingly complex streams over time. Individual differences in structure learning also predicted attention allocation, with better learners attending to complex structures earlier in learning, suggesting that the ability to prioritize different information over time is related to learning success.