The teaching of Probability Theory constitutes a new trend in mathematics education internationally. The purpose of this research project was to explore the degree to which preschoolers understand key concepts of probabilistic thinking, such as sample space, the probability of an event and probability comparisons. At the same time, we evaluated an educational programme which aimed to introduce children to the basic principles of Probability Theory. The research sample consisted of 29 preschoolers (with an average age of 5 years and 4 months) from two classes of a Greek public kindergarten. The research was based on a semi-experimental, three-phase plan: the pretest, the teaching intervention and the post-test. The pretest explored the children's conception of key probabilistic constructs and contributed to the planning of the teaching intervention. Through the post-test, we evaluated the contribution of the teaching intervention. The findings showed that pupils displayed a satisfactory level of comprehension of key probabilistic concepts and that, moreover, teaching this subject can improve their comprehension.