As plant invasions continue to tax ecosystems and threaten biodiversity, it is increasingly important to develop general mechanistic models that can explore the roles of different factors affecting spread. Among the most aggressive invasive species are those dispersed by birds. These plants can move large distances in very short times and, depending on bird habits, be preferentially deposited in favorable habitats. Both birds and plants respond in important ways to heterogeneous habitats, which is critical to predicting the dynamics of invasion. We develop a cellular automata model that uses bird and plant habitat preferences in conjunction with a mechanistically derived seed dispersal kernel to predict broad scale spread patterns. We apply the model to the spread of Celastrus orbiculatus (Oriental bittersweet) by Sturnus vulgaris (European starling) in New England. We parameterize the model with explicit starling movement data and bittersweet survival data in each of four habitat types and compare predictions to historical records describing spread over the last century. Results/Conclusions We find excellent quantitative agreement between our model and patterns of presence and absence that are critically linked to the geometry of heterogeneous habitats. The initial introduction points, and their interaction with the heterogeneous landscape, are among the most important factors producing observed spread patterns. The success of bittersweet in deciduous forests is extremely important in promoting spread, while large patches of coniferous forests in northern New England are relatively impervious to invasion. In spite of dispersal by far-ranging frugivores, random long-distance dispersal is still critical to reproduce patterns of spread. Growth rates are exceptionally high in developed areas, suggesting that anthropogenic cultivation or reintroduction has, and may continue to be, an important contributor to spread.