Using a laboratory analogue of learned fear (Pavlovian fear conditioning), we show that there is substantial heterogeneity across individuals in spontaneous recovery of fear following extinction training. We propose that this heterogeneity might stem from qualitative individual differences in the nature of extinction learning. Whereas some individuals tend to form a new memory during extinction, leaving their fear memory intact, others update the original threat association with new safety information, effectively unlearning the fear memory. We formalize this account in a computational model of fear learning and show that individuals who, according to the model, are more likely to form new extinction memories tend to show greater spontaneous recovery compared to individuals who appear to only update a single memory. This qualitative variation in fear and extinction learning may have important implications for understanding vulnerability and resilience to fear-related psychiatric disorders.