Project complexity is ever growing and needs to be understood and measured better to assist modern project management. The overall ambition of this paper is therefore to define a measure of project complexity in order to assist decision-making. A synthesised literature review on existing complexity measures is proposed in order to highlight their limitations. Then, we identify the multiple aspects of project complexity. We then propose a multi-criteria approach to project complexity evaluation, through the use of the Analytic Hierarchy Process. In the end, it permits to define a relative project complexity measure. Complexity scales and subscales are defined in order to highlight the most complex alternatives and their principal sources of complexity within the set of criteria and sub-criteria which exist in the hierarchical structure. Finally, a case study within a start-up firm in the entertainment industry is performed. Conclusions and research perspectives are given in the end.