To be able to solve complex information problems in a digital environment is a key 21st century skill. Technology users usually expect to achieve their goals in a fast and accurate way. However, the actual relationship between time-on-task and task outcome is currently not well understood. We analyzed data from a large-scale international study in which representative samples of adults had to solve more or less complex problems using standard computer applications. Our results indicate that different task characteristics influence the relationship between problem-solving performance and time-on-task in specific ways. Spending more time on a task is more likely to compensate an average problem solver when task complexity can be attributed to intrinsic task and technology drivers than when complexity stems from the cognitive/metacognitive activities belonging to information problem-solving processes per se, especially acquiring and evaluating information. Thus, the interpretation of time-on-task should take the source of difficulty into consideration. Implications for personal and professional development are discussed.