Biological invasions, including infectious disease outbreaks and biocontrol introductions, often involve small numbers of individuals arriving in spatially heterogeneous environments. Small numbers lead to demographic stochasticity, and spatial heterogeneity means that establishment success depends critically on the introduction sites and movement patterns of invaders. We present a general stochastic modeling framework to address how spatial heterogeneity and movement patterns determine establishment success, population growth, and rates of spatial spread. For dispersal-limited populations, our analysis reveals that spatial heterogeneity increases the expected population growth rate and that local reproductive numbers determine establishment success. Higher dispersal rates decrease the expected population growth rate but can enhance establishment success, particularly when movement patterns are positively correlated with local reproductive numbers. We also find that several small, randomly distributed propagules of invaders are more likely to succeed than a single large propagule. Even if invasions are ultimately successful, there may be substantial time lags before an invader reaches observable densities. These time lags are longer for invasions into patches where extinction risk is high and in landscapes where metapopulation-scale population growth rate is low, while the opposite holds true for rates of spatial spread. Sensitivity analysis of our models provides guidance for control efforts.