Species distribution models (SDMs) have become central tools in ecology and biogeography. Although they can be fitted with different types of species data (e.g. presence-absence, abundance), the most common approach, based on data from large species repositories, is to use simple occurrences (i.e. presence-only) combined with background points (BP; also called pseudo-absences). But how should we sample these background points, and how does this choice affect SDMs? In most studies so far, BP were sampled randomly in geographic space, yet theory rather suggests, if a species is at equilibrium, that it is better to sample them in a stratified way in environmental space. However, this potential improvement of SDM predictions has never been tested. Furthermore, a typical assumption behind SDMs is that the modelled species are at equilibrium with their environment. But how do these models perform when species are in disequilibrium, as is the case for most invasive species? To answer these questions, we selected 30 different species (10 insects, 10 mammals and 10 plants; for each group 5 were invasive and 5 were considered at equilibrium) and for each we calibrated SDMs with different types of background selections: random in environmental space, random-stratified in environmental space, random in geographic space, and random-stratified in geographic space. For each SDM we assessed both predictive performance using standard metrics and their stability using a new approach that compares the model's habitat suitability projection with those of a SDM calibrated with virtual occurrence data generated from the most suitable areas. Finally, we compared the predictive performance of species distribution models of invasive alien (disequilibrium) species versus native (equilibrium) species by comparing model stability and performance metrics of the two groups. We found that sampling BP in a stratified-random way in environmental space yields the highest performance metrics, and that sampling fully randomly in environmental space yields the most stable models. This has implications for the use of SDMs in conservation, as the classical and frequently used fully random in geographic space BP are found to produce both less accurate and less stable models. Our results indicate that the best approach is to use stratified random in environmental space BP sampling if accuracy is essential, and fully random in environmental space BP sampling if model stability is essential.