In past research, project leadership and success have been shown to have a positive correlation. Additionally, an increasing level of project complexity has been observed as having a negative influence on project outcomes. This study attempted to gain further insights into these relationships by utilizing Shenhar and Dvirs' framework of three levels of project complexity, Kouzie and Posners' Leadership Practices Inventory (LPI) survey instrument, and Pinto and Slevin's research on project success. With quantitative survey data from project leaders and stakeholders, the study statistically examined the relationships among leadership, complexity, and success. The surveys, a total of 406, represented 105 distinct projects within six US organizations. The analysis of the data found a significant positive correlation between leadership and project success. Moreover, it found that project complexity moderates the relationship between leadership and internal success while the relationship to external success remains strong throughout all complexity regimes. Finally, analysis of the data supported a single construct for leadership and two distinct (internal and external) constructs for project success.