This paper investigates how complexity influences projects and their performance. We develop a classification of project complexity by relying on fundamental theoretical insights about complexity and then use results from practice-oriented literature to assign concrete project complexity factors to the resulting categories. We also identify specific strategies for organizing and knowledge production that project planners use to address complexity-related uncertainties. We theorize about the way these strategies interact with various types of complexity to increase project performance. Anticipated influences are mostly corroborated using survey data on 81 complex projects from five continents and a diversity of sectors.