Efficient and accurate prediction of dementia in the preclinical stage is important for social and medical reasons. The foregoing literature review suggests that associative memory may serve as a tool for early detection of individuals who may develop dementia later in life. Individuals with mild cognitive impairment (MCI) may be in a transitional stage between normal aging and dementia. The primary goal of the current study was to systematically investigate associative memory in healthy younger adults, healthy older adults, and individuals with Amnestic MCI. We further examined heterogeneity in frontal functioning documented in literature and its relationship with the performance on associative memory among older individuals. Thirty-five older adults (11 with Amnestic MCI) and 20 younger adults completed a series of associative memory experiments which assessed associations between information of the same kind (word-word pairs), associations between different kinds of information (e.g., object-location pairs), and relational associations (an association established between two items through a third item). Additionally, each participant completed a neuropsychological screening battery which served the purpose of classification into different groups (Amnestic MCI or healthy control). Results revealed that older adults with Amnestic MCI demonstrated the greatest and a disproportionate impairment of associative memory with relatively spared item memory. Second, the impaired associative memory was found in all kinds of associative memory tasks. Third, the results suggest that normal healthy old adults, but not MCI individuals, benefited from explicit encoding instruction when performing associative memory. Furthermore, free recall compared to recognition was a more sensitive paradigm when examining the associative memory. Finally, a parallel analysis on groups established by the older individuals’ functional level (high vs. low) in the frontal/executive functioning and medial temporal lobe functioning revealed that the medial temporal lobe function is critical for associative memory. The level of frontal/executive function became important only when the integrity of the medial temporal lobe was compromised. Overall, our results suggest that associative memory functioning may serve as a reliable and sensitive indicator for early detection of people who may develop dementia later in life.