In this study we describe changes of gene expression that occur in the basolateral complex of the mouse amygdala (BLA) during the formation of fear memory. Through the combination of a behavioral training scheme with polymerase chain reaction-based expression analysis (subtractive hybridization and virtual Northern analysis) we were able to identify various gene products that are increased in expression after Pavlovian fear conditioning and are of potential significance for neural plasticity and information storage in the amygdala. In particular, a key enzyme of monoamine metabolism, aldehyde reductase, and the protein sorting and ubiquitination factor Praja1, showed pronounced and learning-specific induction six hours after fear conditioning training. Aldehyde reductase and Praja1, including a novel alternatively spliced isoform termed Praja1a, were induced in the BLA depending on the emotional stimulus presented and showed different expression levels in response to associative conditioning, training stress, and experience of conditioned fear. Stress and fear were further found to induce various signal transduction factors (transthyretin, phosphodiesterase1, protein kinase inhibitor-alpha) and structural reorganization factors (e.g., E2-ubiquitin conjugating enzyme, neuroligin1, actin, UDP-galactose transporter) during training. Our results show that the formation of Pavlovian fear memory is associated with changes of gene expression in the BLA, which may contribute to neural plasticity and the processing of information about both conditioned and unconditioned fear stimuli.