In language learning, learners engage with their environment, incorporating cues from different sources. However, in lab-based experiments, using artificial languages, many of the cues and features that are part of real-world language learning are stripped away. In three experiments, we investigated the role of positive, negative, and mixed feedback on the gradual learning of language-like statistical regularities within an active guessing game paradigm. In Experiment 1, participants received deterministic feedback (100%), whereas probabilistic feedback (i.e., 75% or 50%) was introduced in Experiment 2. Finally, Experiment 3 explored the impact of mixed probabilistic feedback (33% positive, 33% negative, 33% no feedback). The results showed that cross-situational learning of words was observed without feedback, but participants were able to learn structural regularities of the miniature language only when feedback was provided. Interestingly, the presence of positive feedback was particularly helpful for the learner, promoting more in-depth learning of the artificial language.