Ecological invasions are a major worldwide problem exacting tremendous economic and ecological costs. Efforts to explain variability in invasion speed and impact by searching for combinations of ecological conditions and species traits associated with invasions have met with mixed success. We use a simulation model that integrates insights from life-history theory, animal personalities, network theory, and spatial ecology to derive a new mechanism for explaining variation in animal invasion success. We show that spread occurs most rapidly when (1) a species includes a mix of life-history or personality types that differ in density-dependent performance and dispersal tendencies, (2) the differences between types are of intermediate magnitude, and (3) patch connections are intermediate in number and widely spread. Within-species polymorphism in phenotype (e.g., life-history strategies or personality), a feature not included in previous models, is important for overcoming the fact that different traits are associated with success in different stages of the invasion process. Polymorphism in sociability (a personality type) increases the speed of the invasion front, since asocial individuals colonize empty patches and facilitate the local growth of social types that, in turn, induce faster dispersal by asocials at the invasion edge. The results hold implications for the prediction of invasion impacts and the classification of traits associated with invasiveness.