Computing as a discipline has common roots with mathematics and written languages, and computing as a way of thinking and handling has been integral to human culture since ever. This is not only a reasonable argument for convincing society to consider informatics as one of the very fundamental pillars of education, but it also puts the potential contributions of teaching informatics in schools into the correct perspective in the context of science and humanities. Many European countries are switching from teaching information technologies to informatics education during the current second decade of this century. Informatics curriculum is becoming a central part of school education. We explain and design a way of developing informatics curriculum that offer the critical competences new generations need to survive and thrive in todays’ knowledge society and will allow them to contribute to the future development of society. These competences also strongly support the development of their intellectual potential and creativity. Our design of informatics curriculum takes into account the interaction with other scientific disciplines as well with the subject didactics, pedagogy and psychology. The starting point is merging constructionism and critical thinking. Constructionism with its “learning by doing” and “learning by getting things to work” enables designing a teaching process in which students acquire knowledge by creating products, analysing the properties and the functionality of their own products, and finally derive motivation to improve these products. Critical thinking asks us not to teach products of science and technology and their application, but to teach the creative process of their development. To implement this approach, we use the historical method allowing the students to learn by productive failures in the process of searching for a solution. To organize the process of learning and make the different steps available to the appropriate age groups we take into account the cognitive dimensions of the revised taxonomy of Bloom. To illustrate how the combination of all these concepts works we present a detailed curriculum for algorithm design, programming, robotics, and communication in networks.