What is the developmental trajectory of probability learning in early childhood, and how do changes in choice behavior relate to changes in executive functions? We conducted a two-year longitudinal study with children between the ages of 3.5 and 6.5 years and complemented behavioral analyses with computational modeling to illuminate underlying cognitive processes. On average, children became more likely to choose the high-probability option as they grew older and increasingly diversified choices in line with probability matching by T3. Moreover, younger children in the cohort were more likely to maximize probability than older children. Our analyses suggest that increasing choice diversification across childhood may relate to improving executive functions and value-based learning, whereas probability maximizing may serve as an easily implementable satisficing strategy. Finally, our findings emphasize how children's variability in choice behavior may affect the estimated direction of change and highlight the need for longitudinal research.