This study examined how embodied learning experiences support students to grasp abstract CT concepts in early primary education. Forty-seven students were recruited from first- and second-grade classrooms. They had five embodied activities that simulated robot programming tasks requiring students to (1) figure out a route from a starting point to a destination, (2) convert the spatial information into codes, and (3) perform spatial movements according to the codes. The results revealed that students’ CT and spatial reasoning skills significantly improved after the embodied learning. No gender differences were confirmed regarding learning outcomes and attitudes. The students’ ages were closely related to their learning outcomes. The effects of embodied learning, differences between genders, and cognitive development of students were discussed.