Educators and policy makers have increasingly recognized the importance of computational thinking (CT). Despite the growing body of CT literature, how to cultivate CT is still underexplored and undertheorized in early childhood education. Informed by Piaget's Theory of Cognitive Development, this exploratory study was conducted with a focus on three CT skills: pattern recognition, sequencing, and algorithm design. The framework for the study was developed in two stages. First, we designed two sets of unplugged activities (relying on tangible materials), aiming to (1) provide students with more concrete experiences of CT and (2) equip them with the necessary vocabularies/instructions for the subsequent plugged activity (with a digital device). The theoretical foundation for such an unplugged and plugged design comprised Piaget's Theory of Cognitive Development and Asher's Total Physical Response. In the second stage, we offered our CT course in a kindergarten in Hong Kong, involving six teacher participants and a total of 11 students from K1 to K3 (aged 3 to 6). After 10 h of CT training, almost all students demonstrated their mastery of pattern recognition and sequencing. However, the K1 students could only partially complete the tasks of algorithm design while the others generally reached the target level of achievement. Strengthening preschoolers' training on CT language and differentiated instruction are some possible strategies to improve the CT instructions.