In response to tumor necrosis factor (TNF), NF-κB enters the nucleus and promotes inflammatory and stress-responsive gene transcription. Because NF-κB deregulation is associated with disease, one might expect strict control of NF-κB localization. However, nuclear NF-κB levels exhibit considerable cell-to-cell variability, even in unstimulated cells. To resolve this paradox and determine how transcription-inducing signals are encoded, we quantified single-cell NF-κB translocation dynamics and transcription in the same cells. We show that TNF-induced transcription correlates best with fold change in nuclear NF-κB, not absolute nuclear NF-κB abundance. Using computational modeling, we find that an incoherent feedforward loop, from competition for binding to κB motifs, could provide memory of the preligand state necessary for fold-change detection. Experimentally, we observed three gene-specific transcriptional patterns that our model recapitulates by modulating competition strength alone. Fold-change detection buffers against stochastic variation in signaling molecules and explains how cells tolerate variability in NF-κB abundance and localization.