In the contemporary digital era, introducing computational thinking concepts is considered an imperative need at all stages of schooling, since they are inextricably linked to skills applicable and beneficial in everyday life. This chapter presents a novel educational framework that aims to foster the growth of computational thinking at early childhood stages, within the context of physical and natural science courses, pursuing the unplugged philosophy and following the principles of game-based, project-based and collaborative learning. This chapter also presents a relevant pilot study, conducted with second grade students of a Greek primary school, with the objective of assessing the feasibility of the proposed educational framework, as well as examining its effectiveness. The results stemming from the pilot are promising and reveal that the proposed approach serves our goal to enhance computational thinking at the first stages of schooling through engaging and fun educational activities that appeal to young students.