An Algerian highway megaproject has been assessed – to what extent and how it is successful – based on five measures; the main success was more on the tactical and strategic levels measured in terms of effectiveness, relevance, impact and sustainability. Many internal and external stakeholders contributed to the failure of this megaproject at the operational level measured in terms of efficiency. This paper will list all possible external and internal stakeholders of this megaproject and subsequently identify the relationship between each stakeholder and the five measures. A stakeholder mapping and the interpretation of a power / interest matrix are used to identify and analyze the relationship between stakeholders and the effect of their actions at each level of the megaproject. The case shows that an early involvement of the key stakeholders will contribute positively to all the five measures.