Purpose: The purpose of this study was to report how "verbal rehearsal speed" (VRS), a form of covert speech used to maintain verbal information in working memory, and another verbal processing speed measure, perceptual encoding speed, are related to 3 domains of executive function (EF) at risk in cochlear implant (CI) users: verbal working memory, fluency-speed, and inhibition-concentration. Method: EF, speech perception, and language outcome measures were obtained from 55 prelingually deaf, long-term CI users and matched controls with normal hearing (NH controls). Correlational analyses were used to assess relations between VRS (articulation rate), perceptual encoding speed (digit and color naming), and the outcomes in each sample. Results: CI users displayed slower verbal processing speeds than NH controls. Verbal rehearsal speed was related to 2 EF domains in the NH sample but was unrelated to EF outcomes in CI users. Perceptual encoding speed was related to all EF domains in both groups. Conclusions: Verbal rehearsal speed may be less influential for EF quality in CI users than for NH controls, whereas rapid automatized labeling skills and EF are closely related in both groups. CI users may develop processing strategies in EF tasks that differ from the covert speech strategies routinely employed by NH individuals.