A recent report by the joint Informatics Europe & ACM Europe Working Group on Informatics Education emphasizes that: (1) computational thinking is an important ability that all people should possess; (2) informatics-based concepts, abilities and skills are teachable, and must be included in the primary and particularly in the secondary school curriculum. Accordingly, the "2013 Best Practices in Education Award" (organized by Informatics Europe) was devoted to initiatives promoting Informatics Education in Primary and Secondary Schools. In this paper we present one of the winning projects: "Multi-Sensory Informatics Education". We have developed effective multi-sensory methods and software-tools to improve the teaching-learning process of elementary, sorting and recursive algorithms. The technologically and artistically enhanced learning environment we present has also the potential to promote intercultural computer science education and the algorithmic thinking of both science- and humanities-oriented learners.