Artificial Intelligence has rapidly captured—again—the attention of practitioners and the CS Education community. Consequently, several initiatives worldwide have been spawning recently to identify effective ways to introduce learners at college and high-school levels to the basics of AI. In this context, we developed Scratch-NB, an extension to the Scratch programming language to equip K-8 learners with foundational tools for developing a Naive-Bayes classifier. On the one hand, we opted to use Scratch due to its popularity within the CS4All movement and its predominance in schools. On the other hand, we opted to provide a simple implementation of the Naive Bayes classifier as a gateway for introducing basic notions of supervised learning and AI in general. In this paper, we report the design rationale of our tool and our experience of using it in an informal workshop with children aged 10-12 with no prior knowledge of computational thinking, coding, or AI. The obtained results show that Scratch-NB showed high levels of acceptance among the participants, raised interest in AI, and effectively provided basic foundations in the area, particularly when comparing Scratch-NB with other state-of-the-art tools targeted to this learner group, such as Machine Learning for Kids. We argue that our tool has the potential to illuminate further practical and research endeavors when exploring how to effectively introduce younger populations to the foundational notions of AI in practical contexts.