Individuals hold different mindsets encompassing beliefs about trait stability (stable vs. malleable) and goal orientations (performance vs. mastery). These motivational beliefs affect behavioral self-regulation, which is an important predictor of school success and includes both executive functions (EF) and classroom behavioral self-regulation (CBSR). In this study, we examined the structure of mindsets in kindergarteners and the relations with EF and CBSR by interviewing 147 kindergarteners (51% female) aged 5 to 7 years (M = 6.47, SD = 0.39). We used a multimethod approach with self-report and direct measures of behavioral self-regulation, achievement, and a newly developed mindset scale. Exploratory and confirmatory factor analyses revealed that trait beliefs and goal orientations represent two different but related motivational beliefs. Results indicated differential effects of trait beliefs and goal orientations on EF and CBSR: Children with a mastery (vs. performance) orientation showed better EF, whereas children with a belief in traits as malleable (vs. stable) showed better CBSR. Structural equation modeling showed significant indirect effects of both motivational beliefs on achievement, with EF and CBSR as mediators. Findings suggest that motivational beliefs are important in fostering behavioral self-regulation for successful adjustment to the demands of kindergarten.