Despite the need for sentinel cells to respond to temporally evolving pathogenic and host signals, it is still unclear whether memory of previous signals shapes the response of sentinel cells to new stimulus. Many of the inflammatory stimuli which sentinel cells respond to converge on information bottlenecks during signal transduction. How individual cells extract information about fluctuating signals from these limited networks is unknown. Is memory predictable and determined by initial cell state or random and due to inherent biological stochasticity? Characterization of signaling memory in individual sentinel cells would enable new approaches to targeting pathogenic and programming desired memory states in disease. Here, we systematically profile stimulus memory in individual cells using automated microfluidics, live cell imaging, mathematical cells, and gene expression and chromatin profiling. We show that memory in single cells is encoded in NFκB activation dynamics, and that this memory is deterministic and predictable by prior stimulus response. In fibroblasts, this memory is dependent on overlap between inflammatory signaling pathways, whereas in macrophages, memory is broadly encoded for all stimuli. Combining stimulus-dependent remodeling of NFκB activation dynamics and chromatin accessibility explains the transcriptomic landscape of memory-conditioned macrophages. These results demonstrate that single sentinel cells can encode memory in signaling dynamics which play a key role in shaping the functional state of the cell.