Few individuals are up-to-date on COVID-19 vaccines, leading to widespread gaps in protection. Current vaccine communication strategies emphasize availability, with limited effectiveness for motivating recurring vaccinations and vaccine-hesitant individuals. To address this gap, we developed an intervention that targeted beliefs about immunity, providing personalized feedback about likely protection against COVID-19. In an online sample of participants (N=882, stratified by age and gender), this intervention effectively changed immunity beliefs and increased vaccination intentions. Two months later, belief changes endured, and self-reported vaccine uptake was approximately 8x higher than the US-national rate during the same time period. Importantly, our intervention was substantially more effective than existing, non-personalized interventions used by national public health organizations. We then scaled our intervention to a public website and replicated our findings in a nationally-representative sample (N=553). Overall, our novel psychological intervention changed immunity beliefs and motivated vaccination, of relevance for COVID-19, influenza, and future pandemic threats.