Changes to everyday spoken language (“connected language”) are evident in persons with AD dementia, yet little is known about when these changes are first detectable on the continuum of cognitive decline. The aim of this study was to determine if participants with very early, subclinical memory declines were also showing declines in connected language. We analyzed connected language samples obtained from a simple picture description task at two time points in 264 participants from the Wisconsin Registry for Alzheimer’s Prevention (WRAP). In parallel, participants were classified as either “Cognitively Healthy” or “Early Mild Cognitive Impairment” based on longitudinal neuropsychological test performance. Linear mixed effects models were used to analyze language parameters that were extracted from the connected language samples using automated feature extraction. Participants with eMCI status declined faster in features of speech fluency and semantic content than those who were cognitively stable. Measures of lexical diversity and grammatical complexity were not associated with eMCI status in this group. These findings provide novel insights about the relationship between cognitive decline and everyday language, using a quick, inexpensive, and performance-based method.