The cholinergic system has extensive projections to the olfactory bulb (OB) where it produces a state-dependent regulation of sensory gating. Previous work has shown a prominent role of muscarinic acetylcholine (ACh) receptors (mAChRs) in regulating the excitability of OB neurons, in particular the M1 receptor. Here, we examined the contribution of M1 and M3 mAChR subtypes to olfactory processing using mice with a genetic deletion of these receptors, the M1-/- and the M1/M3-/- knockout (KO) mice. Genetic ablation of the M1 and M3 mAChRs resulted in a significant deficit in odor discrimination of closely related molecules, including stereoisomers. However, the discrimination of dissimilar molecules, social odors (e.g., urine) and novel object recognition was not affected. In addition the KO mice showed impaired learning in an associative odor-learning task, learning to discriminate odors at a slower rate, indicating that both short and long-term memory is disrupted by mAChR dysfunction. Interestingly, the KO mice exhibited decreased olfactory neurogenesis at younger ages, a deficit that was not maintained in older animals. In older animals, the olfactory deficit could be restored by increasing the number of new born neurons integrated into the OB after exposing them to an olfactory enriched environment, suggesting that muscarinic modulation and adult neurogenesis could be two different mechanism used by the olfactory system to improve olfactory processing.