Coincidences are surprising concurrences of rare or unlikely events, with no apparent cause. Paradoxically, coincidences are reported quite often, which is explained by different factors such as psychological biases and hidden causes, but also mathematically. For example, it can be shown from combinatorics that some “surprising” events like matching birthdays are expected under common circumstances, which illustrates how our intuition is not good at estimating these chances. In this chapter, I examine another mathematical factor that may explain some coincidences, namely, Kolmogorov complexity and algorithmic probability. In brief, I show how the varying complexity of different numbers or patterns can make certain outcomes more likely than others, thereby reducing the entropy of the probability distributions, and hence increasing the chances of coincidences. I study the index of coincidence (probability of matches) for integers and patterns, convergent evolution in biology, and time series patterns. For the latter, I further study coincidences in anomalies, that is, two independent series simultaneously defying an observed trend. Additionally, I point to an intriguing connection to uncomputability, namely, that, in some cases, it would not be possible to know how likely a given coincidence was, adding a peculiar twist to curious coincidences.