The ability to associate memorized objects with their location in space gradually declines during normal aging and can drastically be affected by neurodegenerative diseases. This study investigates object-location paired-associates learning (PAL) in the grey mouse lemur (Microcebus murinus), a nonhuman primate model of brain aging. Touchscreen-based testing of 6 young adults (1-5 years) and 6 old adults (> 7 years) in the procedural rodent dPAL-task revealed significant age-related performance decline, evident in group differences in the percentage of correct decision during learning and the number of sessions needed to reach a predefined criterion. Response pattern analyses suggest decreased susceptibility to relative stimulus-position biases in young animals, facilitating PAL. Additional data from a subset of "overtrained" individuals (n = 7) and challenge sessions using a modified protocol (sPAL) further suggest that learning criteria routinely used in animal studies on PAL can underestimate the endpoint at which a stable performance is reached and that more conservative criteria are needed to improve construct validity of the task. To conclude, this is the first report of an age effect on dPAL and corroborates the role of mouse lemurs as valuable natural nonhuman primate models in aging research.