Biological invasions are a major threat to natural communities worldwide. While several species traits have been identified as important determinants of invasion success, a systematic exploration of the effects of invasions on native communities, and the role of species and community features on community robustness in the face of invasion is lacking. We present a theoretical approximation considering food web structure and species population dynamics to study the effects of invasions on complex food webs. We find that less complex (i.e., less connected) food webs are more resistant to invasions. Simulated invasions promote profound changes in several food web properties and stability measures, such as decreases in modularity and the number of food chains from basal to top species; and a decoupling of community- and population-level temporal variability. Additionally, species traits such as body size and diet breadth are strong determinants of invasion success across several trophic levels, with larger and more generalist species being more successful invaders in general. Our work complements species-centered invasion studies by adding a more holistic and systematic perspective to the study of invasions on species interaction networks.