The campaign to build the Tombeau du Martyr Juif Inconnu in Paris (today Mémorial de la Shoah) in the 1950s transcended both national and religious barriers. Without denying the Jewish significance of the genocide, this campaign targeted various religious communities and received international political support. However, while the Holocaust today has become a catalyst for critical reflection on national shame and guilt, this article suggests that the emergence of this remembrance in the early Cold War era did not necessarily challenge or deconstruct existing heroic national narratives of the past. By associating the commemoration of this genocide with positive deeds and intercultural solidarity, the whole project was indeed successful.