Abstract Understanding how the spatial variation in species composition (beta-diversity) varies with biotic and abiotic conditions is one of the ultimate goals in biology. Theory predicts that beta-diversity is a consequence of two factors, species-level differences (defined as the variations among species in the probabilities that species are present in the landscape) and spatial heterogeneity (defined as the difference, between two sites, in the probabilities with which species are present). At present, however, the importance of each factor is unclear. Here, we take a probabilistic and combinatorial approach to examine the effects of species differences and spatial heterogeneity on the degree to which species assemblages in two spatial locations differ in species compositions. We first derived analytical and approximation formulae of the expectation and variance of the pairwise beta-diversity, based on the assumption that the presence probabilities of species are independent of each other. Though it seems intuitive that greater species differences leads to greater beta-diversity, our methods predict that the reverse is likely to occur under some circumstances; strikingly, when space is homogeneous, beta-diversity decreases with increasing species differences. This prediction suggests that policy making for increasing species traits-variation would, without adequately managing environmental heterogeneity, induce biotic homogeneization, resulting in undesired outcomes. Second, we illustrate our method using data from five woodpecker species in Switzerland, showing that the woodpecker species’ joint distributions change considerably with time, and also that such changes are basically explained by the changes in the incidences of some of the species. The new framework can improve our understanding of how pairwise beta-diversity responds to species differences and spatial heterogeneity.