Olfactory dysfunction is a prevalent symptom and an early marker of age-related neurodegenerative diseases in humans, including Alzheimer's and Parkinson's Diseases. However, as olfactory dysfunction is also a common symptom of normal aging, it is important to identify associated behavioral and mechanistic changes that underlie olfactory dysfunction in nonpathological aging. In the present study, we systematically investigated age-related behavioral changes in four specific domains of olfaction and the molecular basis in C57BL/6J mice. Our results showed that selective loss of odor discrimination was the earliest smelling behavioral change with aging, followed by a decline in odor sensitivity and detection while odor habituation remained in old mice. Compared to behavioral changes related with cognitive and motor functions, smelling loss was among the earliest biomarkers of aging. During aging, metabolites related with oxidative stress, osmolytes, and infection became dysregulated in the olfactory bulb, and G protein coupled receptor-related signaling was significantly down regulated in olfactory bulbs of aged mice. Poly ADP-ribosylation levels, protein expression of DNA damage markers, and inflammation increased significantly in the olfactory bulb of older mice. Lower NAD+ levels were also detected. Supplementation of NAD+ through NR in water improved longevity and partially enhanced olfaction in aged mice. Our studies provide mechanistic and biological insights into the olfaction decline during aging and highlight the role of NAD+ for preserving smelling function and general health.