With further emancipation of once subdued or marginalized stakeholders, a growing number of megaprojects face increasingly significant social resistance. Asymmetries of support for the projects emerge, rooted in different perceptions of legitimacy across different stakeholder groups. In this paper, we ask how these diverging perceptions of legitimacy develop across stakeholders of cross-border megaprojects. We conduct a multi-site ethnography at one of the biggest contemporary cross-border transport megaprojects in the world – the Danish/German Fehmarnbelt Fixed Link. Tying together three streams of the legitimacy literature in a new analytical approach, we suggest three dimensions of project legitimacy perception: trust, majority, and morality. In doing so, we provide a new integrative model of legitimacy perception in megaprojects. We illustrate how these legitimacy dimensions dynamically interact. We thus provide new insights on how project legitimacy is continuously renegotiated in megaprojects with implications for future developments of project governance.