This study examines the extent to which simultaneous olfactory discrimination learning increases spine density on hippocampal CA1 pyramidal neurons in C57BL/6J (C57) and DBA/2J (DBA) inbred mice, characterized by spontaneous differences in hippocampal plasticity and hippocampus-related learning. The behavioral data first showed a clear-cut difference in performance between the two strains. C57 mice learned to identify the positively reinforced olfactory cue whereas DBA did not. Both strains, however, similarly acquired the procedural aspects of the task. The morphological analysis performed 24 h post-training revealed that spine density was significantly increased along apical, oblique, and basal dendrites in trained C57 mice compared to trained DBA mice, and to pseudotrained as well as to control cage mice of both strains. These findings confirm the ability of C57 mice to solve hippocampal-dependent tasks and provide the first evidence that simultaneous olfactory discrimination learning elicits spine growth in the mouse hippocampus. In addition, the finding that DBA mice failed to discriminate between the two olfactory cues but were as efficient as C57 mice in learning the procedural aspects of the task outlines that the structural changes observed in the latter strain were independent from any procedural learning component.