Summary Invasive species usually start out as small colonizing populations that are prone to extinction through demographic stochasticity and Allee effects, leading to a positive relationship between establishment probability and founding population size. However, establishment success also depends on the environment to which species are introduced: for a given species, some locations will be more favourable for establishment than others. We present equations for modelling the expected relationship between establishment probability and founding population size when demographic stochasticity, Allee effects and, for the first time, environmental heterogeneity are operating. We show that heterogeneity in environmental conditions can change the shape of the relationship between establishment probability and founding population size through a disproportionate decline in the probability of establishment in larger populations, the opposite of an Allee effect. This outcome is likely in most empirical data sets relating founding population size to establishment probability, and highlights that unfavourable environments are often the major cause of establishment failures. It also emphasizes the insights that can be gained from applying models with a theoretical underpinning.