Although widely recognized both in literature and among practitioners, project complexity may cause poor project success, with little empirical evidence supporting this contention. Therefore, this study analyzed, for the first time, the relationship between project complexity and success in complex construction projects and investigated how project complexity affects project success. First, project complexity is hypothesized to be negatively related to project success. Second, on the basis of literature review and expert interviews, a total of 245 questionnaire surveys on project complexity and project outcomes were collected in China. Project complexity was measured as information, task, technological, organizational, environmental, and goal complexities by correlation and factor analyses. Finally, the structural-equation modeling technique was used to test the hypothesis and explore the effect of different complexities on project success. The findings of this study support the hypothesized negative relationship between the complexity and success of complex construction projects. Furthermore, information complexity and goal complexity have significant negative effects on project success. The research would have significant theoretical and practical significance for improving the theory of complex project management and achieving project success in complex construction projects for project managers.