Executive functions (EF) are domain-general cognitive skills that predict foundational academic skills such as literacy and numeracy. However, less is known about the relation between EFs and science achievement. The nature of this relation might be explained by the theory of mutualism, which states that development is the result of complex and interacting processes, in which growth in one domain influences growth in another domain. The present study examined the bidirectional associations between science achievement and children's cognitive flexibility and working memory in a nationally representative sample of children in the United States (Early Childhood Longitudinal Study: Kindergarten Class of 2010-2011 [ECLS-K:2011]; N = 18,174). Using random intercepts cross-lagged panel modeling, results revealed a heterogeneous pattern of associations between EF and science achievement, consistent with mutualism theory. Trait-like and construct stability emerged in the between-person and within-person estimates of EF and science. Cognitive flexibility and working memory in kindergarten each predicted science achievement in first grade. Science achievement at the beginning of first grade predicted cognitive flexibility at the end of first grade. There were also bidirectional associations between working memory and science achievement from the beginning to the end of the first grade year. Although effect sizes were small, findings reveal the complex interplay between EF and science achievement during early childhood and highlight a core tenet of mutualism theory--that small gains in academic and cognitive domains are positively associated with future skills and abilities within and across domains.