Probabilistic phonotactics refers to the frequency with which segments and sequences of segments occur in syllables and words. Knowledge of phonotactics has been shown to be an important source of information in recognizing spoken words in listeners with normal hearing. Two online tasks (an auditory same-different task and an auditory lexical decision task) were used to examine the use of phonotactic information by adults who were postlingually deafened who have received cochlear implants. The results of the experiments showed that cochlear implant patients with better word recognition abilities (as measured by the Northwestern University Auditory Test No. 6 (NU-6) produced patterns of results that were similar to the pattern of results obtained from listeners with normal hearing in Vitevitch and Luce (1999). This finding suggests that cochlear implant patients with better word recognition abilities use lexical and sublexical representations to process spoken words, much like listeners with normal hearing. In contrast, cochlear implant patients with poor word recognition abilities could not differentiate between stimuli varying in phonotactic probability and lexicality, suggesting that less distinct representations are used by these patients to process spoken words. The implications of these results for outcome assessments and clinical interventions are discussed.