In fear conditioning, shock training (ST) and shock-associated fearful cues (FC) produce relatively selective decreases in rapid eye movement sleep (REM) in mice that vary with strain, and can last for an extended period. We examined sleep in BALB/cJ mice over 6 h after ST and FC, and in handling and tone control conditions. In separate groups of mice, we used immunohistochemical techniques to examine Fos expression in limbic and brainstem regions involved in fear conditioning and in the regulation of REM in 2-h intervals over this period. Significant reductions in REM were observed at 2 and 4 h after ST. Fos expression in the brainstem was significantly elevated at 2 h after ST in the laterodorsal and peduculopontine tegmentum, up to 4 h in the dorsal raphe nucleus (DRN) and up to 6 h in the locus coeruleus (LC). Significant elevations in Fos expression were observed in several regions of the amygdala up to 4 and 6 h after ST. Decreases in REM after FC were significant at 2 h. Increased Fos expression was observed in LC at 2 h and in DRN up to 6 h after FC. Increased Fos expression in the amygdala was observed in several regions of the amygdala at 2 h after FC, but not longer. Significant changes in Fos expression in the central nucleus of the amygdala were not observed at any time point examined or in any condition. The data are discussed with respect to the putative role of brainstem nuclei in regulating REM and the role of the amygdala in conditioned fear.