The encoding or retrieval of a contextual fear memory recruits the activity of thousands of neurons across the mammalian brain. This ensemble of cells is often identified by immediate-early genes (IEGs), which are expressed following neuronal activity, but the extent to which the expression pattern of one IEG reflects another is unclear. Here, we examined the IEGs Arc/Arg3.1 and c-Fos across several brain regions during fear memory encoding or retrieval. Mice were administered a 3-shock contextual fear conditioning (CFC) paradigm and sacrificed 1h later (encoding), 1 h after context re-exposure 1 day later (1-day retrieval), or 1 h after context re-exposure 5 days later (5-day retrieval) (n = 8 per group). Brain tissue was immunostained for Arc and c-Fos protein. We found that the two IEGs showed stark differences in expression, with fewer than 50% of Arc+ or c-Fos+ cells in any brain region expressing both markers. While c-Fos+ cell density remained constant across memory states in both CA3 and the dentate gyrus (DG) of the hippocampus, Arc+ cell density increased from encoding to retrieval in CA3 yet remained constant in the DG. In subcortical areas like the basolateral amygdala complex (BLA) and the paraventricular nucleus of the thalamus (PVT), expression of Arc and c-Fos did not vary with memory state, but c-Fos expression exceeded that of Arc across all states. Our results warrant further study of the conditions that induce expression of these markers, and they suggest that ensembles identified by either IEG may be anatomically or functionally distinct.