The degree to which evolutionary trajectories and outcomes are repeatable across independent populations depends on the relative contribution of selection, chance and history. Population size has been shown theoretically and empirically to affect the amount of variation that arises among independent populations adapting to the same environment. Here, we measure the contribution of selection, chance and history in different-sized experimental populations of the unicellular alga Chlamydomonas reinhardtii adapting to a high salt environment to determine which component of evolution is affected by population size. We find that adaptation to salt is repeatable at the fitness level in medium (Ne = 5 × 104) and large (Ne = 4 × 105) populations because of the large contribution of selection. Adaptation is not repeatable in small (Ne = 5 × 103) populations because of large constraints from history. The threshold between stochastic and deterministic evolution in this case is therefore between effective population sizes of 103 and 104. Our results indicate that diversity across populations is more likely to be maintained if they are small. Experimental outcomes in large populations are likely to be robust and can inform our predictions about outcomes in similar situations.