Recent political contests across Europe and North America have been propelled by a wave of populist, anti-immigrant resentment, and it was widely expected that these populist victories would further fan the flames of xenophobia. We implemented an experimental design around the Brexit referendum to test how populist victories shape anti-immigrant attitudes. We find that anti-immigrant attitudes actually softened after the Brexit referendum, among both Leave and Remain supporters, and these effects persisted for several months. How could a right-wing, populist victory soften anti-immigrant attitudes? We use causal mediation analysis to understand this `populist paradox.' Among Leavers, a greater sense of control over immigration channelled the effects of the Brexit outcome onto anti-immigrant attitudes. But it is individuals' efforts to distance themselves from accusations of xenophobia and racism that explains why we see a softening of attitudes towards immigration among both Leavers and Remainers.