The 21st-century work environment places strong emphasis on nonroutine transversal skills. In an educational context, complex problem solving (CPS) is generally considered an important transversal skill that includes knowledge acquisition and its application in new and interactive situations. The dynamic and interactive nature of CPS requires a computer-based administration of CPS tests such that the assessment of CPS might be partially confounded with information and communication technology (ICT) literacy. To establish CPS as a distinct construct that involves complex cognitive processes not covered by other general cognitive abilities and not related to ICT literacy, it is necessary to investigate the influence of ICT literacy on CPS and on the power of CPS to predict external educational criteria. We did so in 3 different samples of either high school or university students using a variety of instruments to measure ICT literacy and general cognitive ability. Convergent results based on structural equation modeling and confirmatory factor analyses across the studies showed that ICT literacy was weakly or moderately related to CPS, and these associations were similar to those between ICT and other general cognitive abilities. Furthermore, the power of CPS to predict external educational criteria over and above general cognitive ability remained even if the influence of ICT literacy on CPS was controlled for. We conclude that CPS is a distinct construct that captures complex cognitive processes not generally found in other assessments of general cognitive ability or of ICT literacy.