Project complexity is usually considered as one of the main causes of cost overruns, resulting in poor performance and thus project failure. However, empirical studies focused on evaluating its effects on project cost remain lacking. Given this circumstance, this study attempts to develop the relationship between project cost and the multidimensional project complexity elements. The study assumes complexity as a multidimensional factor including the task, organization, market, legal, and environment complexities. An empirical evidence-based structural model was adopted to account for the relationships between project cost and project complexity. By doing so, a quantitative assessment of multidimensional project complexity was developed. Findings suggest that task and organization complexities have direct effects on project cost; while market, legal, and external environment complexities have indirect effects on project cost. Key practical contribution is that the findings can improve the understanding of which dimensions of complexity significantly influence project cost and the need to focus efforts on strategically addressing those complexities.