Evolution is the central, unifying, and overarching theme in biology. Nevertheless, researchers have consistently reported that students face conceptual difficulties with their understanding. In particular, those aspects of evolution that are strongly related to abstract concepts like randomness and probability, so-called threshold concepts, are misunderstood. We conducted two studies to test the hypothesis that one central problem of understanding evolution is the comprehension of the abstract concepts of randomness and probability. In the first study, we analyzed the relationships of students’ understanding of randomness and probability with their understanding of evolution. Additionally, three interventions were applied to train students’ understanding of randomness: an animation, a text on randomness, and mathematical tasks. German university students participated in a quasi-experimental pretest-posttest intervention study. Data from the pretest show a significant positive correlation between understanding the concept of randomness and understanding the concept of evolution. In the second study, we focused on developing an instrument to measure students’ understanding of randomness and probability.