In olfactory paired-associate (PA) studies, odors are paired with target stimuli in an initial training session. In a testing session, the odor cues are presented and subjects are asked to recognize the target (among multiple foils) that was initially paired with the odor. Previous olfactory PA studies showed that odors are less effective associative cues than stimuli from other sensory modalities. It has been suggested that odor familiarity might improve odor memory by assisting odor discrimination and facilitating PA memory acquisition. In the current study, we investigated whether getting familiar with odors would also enhance the effectiveness of odors as cues in an olfactory PA test. We designed an experiment with a familiarity manipulation to evaluate the role of odor familiarity in PA memory with odors. There were two groups of participants in the experiments: an experimental group who got familiarized with half of the pre-rated odors (16 odors, 8 high- and 8 low-familiar) in four weeks, and a control group. Both groups ran a PA memory paradigm in which they associated 32 odors (16 high- and 16 low-familiar odors) with black and white complex shapes. We predicted an interaction between pre-rated odors and familiarity training whereby training should only help low familiar odors in such a way that familiarity training would increase their effectiveness in target retrieval over untrained low-familiarity odors. These results provide further evidence for odor familiarity as one of the critical features in olfactory processing and memory.