Data generated by international science examinations such as TIMSS and PISA indicated that many students failed to solve science tasks not because of their lack of specific scientific knowledge, but because of poor general problem solving skills. The present study was triggered by the need to introduce middle-school students to strategies and techniques of working with unfamiliar material and using general symbolic tools. Feuerstein’s theory of Mediated Learning Experience and Vygotsky’s concept of psychological tools served as a theoretical basis for two intervention programs: The first program connected content-neutral cognitive tasks with TIMSS-like science tasks, while the second one offered students a new scientific experience Thinking Journey to the Moon. Middle-school students were pre- and posttested by TIMSS-like tasks that required minimal prior scientific knowledge. Both programs proved to be effective in improving students’ problem solving and the ability to justify their answers, though reflective ability continued to be weaker than problem solving. The relative importance of mediated learning experience vs. specific problem solving tasks is discussed.