While scholars have long studied the relationship between nationalist beliefs and anti-immigrant attitudes, such work has proceeded largely independently from research on collective memory, which explores how nationalist narratives are created, maintained, and contested. In this paper, we bring these literatures together by asking how, at the individual level, receptivity to salient narratives about the nation’s past is associated with dispositions toward immigrants and immigration policy. Specifically, we focus on two narratives common in a number of contemporary democracies that frame the nation as having been perpetually victimised over its history (i.e. the victimhood narrative) and as having been chosen to carry out a special mission in the world (i.e. the exceptionalism narrative). Using original data from Israel, we demonstrate that stronger agreement with these narratives, and particularly with exceptionalism, is associated with greater propensity to hold anti-immigrant views. Our analyses reveal that this relationship is mediated by ethnic conceptions of the nation’s symbolic boundaries and, to a lesser degree, by perceived symbolic and material threats to the nation-state. Building on recent comparative work, we argue that in nations with a history of precarious sovereignty, victimhood and exceptionalism narratives can provide a fertile basis for the exclusionary appeals of radical-right political actors.