Behavior genetics studies in mice demand efficient training protocols for rapid phenotypic screening. However, the capacity of neonatal mice to form and retain associative memories has been difficult to study due to their limited sensorimotor capacities. The present study describes a method for robust, naturalistic associative learning in neonatal mice as young as 3 days old. After removal of the dam from the home cage for 2 h, preweanling CD-1 mice of ages 3, 5, and 10 days postnatal were conditioned to associate an arbitrary odorant with the suckling and milk delivery that ensued upon her return to the home cage. After a second maternal deprivation, neonates were tested on their acquired preference for that odorant. Neonates exhibited a learned preference for the conditioned odorant over a novel control odorant. No learning was observed without deprivation, that is, when the dam was removed only briefly for scenting. One-trial learning sufficed to show clear preferences for the conditioned odorant, although repeated training (three sessions over 8 days) significantly increased the expression of preference. The development of neonatal associative learning protocols requiring minimal human intervention is important for the behavioral phenotyping of mutant and transgenic strains, particularly those modeling developmental disorders.