An adaptive learning system offers a digital learning environment that adjusts itself to the individual learner and learning material. By refining its internal model of the learner and material over time, such a system continually improves its ability to present appropriate exercises that maximise learning gains. In many cases, there is an initial mismatch between the internal model and the learner’s actual performance on the presented items, causing a “cold start” during which the system is poorly adjusted to the situation. In this study, we implemented several strategies for mitigating this cold start problem in an adaptive fact learning system and experimentally tested their effect on learning performance. The strategies included predicting difficulty for individual learner-fact pairs, individual learners, individual facts, and the set of facts as a whole. We found that cold start mitigation improved learning outcomes, provided that there was sufficient variability in the difficulty of the study material. Informed individualised predictions allowed the system to schedule learners’ study time more effectively, leading to an increase in response accuracy during the learning session as well as improved retention of the studied items afterwards. Our findings show that addressing the cold start problem in adaptive learning systems can have a real impact on learning outcomes. We expect this to be particularly valuable in real-world educational settings with large individual differences between learners and highly diverse materials.