Changes in the demands posed by increasingly complex workplaces in the 21st century have raised the importance of nonroutine skills such as complex problem solving (CPS). However, little is known about the antecedents and outcomes of CPS, especially with regard to malleable external factors such as classroom climate. To investigate the relations between CPS and other constructs, we had Finnish 6th-grade students complete a test battery that included CPS tasks, fluid reasoning, classroom climate, and academic outcomes such as school grades and academic potential (N = 1,670). The working memory test was administered to a subsample of students (N = 357). A latent multilevel analysis suggests that (a) fluid reasoning, working memory, and classroom climate influenced CPS skills, and (b) CPS skills exhibited some incremental value in explaining school grades after controlling for cognitive ability, although the largest part of CPS' relations to the outcomes was due to its overlap with other cognitive abilities. Further, on the class level, classroom climate showed a significant indirect effect on school grades via its influence on between-class differences in CPS. On the basis of this pattern of results, we argue that classroom climate is likely to be an important antecedent of CPS skills. Hence, we suggest that future research further explore how CPS is related to malleable factors such as classroom climate and extend analyses on the predictive validity of CPS to include real-world outcomes beyond the academic setting.