Individuals with mild cognitive impairment (MCI) may present with subtle declines in linguistic ability that go undetected by tasks not challenging enough to tax a relatively intact cognitive-linguistic system. This study was designed to replicate and extend a previous study of cognitive-linguistic ability in MCI using a complex discourse production task. Two hypotheses were tested: (a) complex discourse production differentiates individuals with MCI from individuals who are cognitively normal and (b) decreases in complex discourse production ability in MCI are related to declines in the planning and cognitive flexibility components of executive function (EF). Nine adults with MCI and nine age- and gender-matched controls participated in this study. Participants were assessed in terms of general cognition, naming ability, components of EF, and spoken discourse production. Performance on the experimental spoken discourse production task distinguished the groups on a measure of quality but not on length or complexity. The EF component of cognitive flexibility appeared important to discourse production ability. Results of this study provide further support for the use of a complex discourse production task as a tool for early detection of MCI.