Nowadays, there is a high demand for qualified computer scientists and thus, it is important to start increasing computer literacy already at an early age. Although computer science and digital literacy are already becoming dominant topics and are increasingly anchored in the curricula, there is still a mismatch between what students and teachers understand the subjects to be and what they really are. In computer science, in particular, it is often believed that a computer is indispensable for teaching. The authors of this study want to change this picture by conveying basic computer science concepts, which play an essential role in many everyday situations. Thus, it is important to teach them from an early age. The challenge here is to find ways to present these fundamental ideas of computer science creatively so that young children, as well as laypersons, understand them. This paper introduces the COOL Computer Science Circus, which links selected core concepts with a circus show including interactive parts on side of a young audience. Alternatively, the show can be transformed into a workshop. The target group consists not only of primary school students aged 9–10, but also of primary school teachers. The authors describe their experiences and present first results of an ongoing survey which collects feedback to the COOL CS Circus as well as information about the teachers’ interest and perception of computer science and digital education. Moreover, the paper gives an inspiration on how to present topics such as encryption, encoding, and algorithms without the need for a computer.