We investigated the learning of non-adjacent phonotactic dependencies in adult speech perception. Following previous research examining learning of dependencies at a grammatical level (Gomez, 2002), we manipulated the co-occurrence of non-adjacent phonological segments within a spoken syllable. Each listener was exposed to consonant-vowel-consonant (CVC) nonword stimuli produced by one of two phonological grammars. Both languages contained the same adjacent dependencies between the initial CV and final VC sequences but differed on the co-occurrences of initial and final consonants. Two blocks of spoken stimuli were presented to listeners, a training block and a test block. Participants' repeated (or shadowed) the stimuli in both blocks and their learning of non-adjacent segmental dependencies was evaluated by examining their reaction times to repeat the stimuli in the test block as a function of what was presented in the training block. During the test block, participants heard (1) old nonwords on which they had been trained (complete CVC overlap), (2) new nonwords sharing adjacent dependencies with the nonwords on which they had been trained (either CV or VC overlap), (3) new nonwords sharing non-adjacent dependencies with the nonwords on which they had been trained (initial and final C overlap), and (4) new nonwords sharing neither adjacent nor non-adjacent dependencies with the nonwords on which they had been trained (either initial C or final C overlap only). The results provide evidence that listeners are sensitive to nonadjacent phonotactic dependencies in the perception of spoken language. In particular, participants were faster to repeat nonwords with the non-adjacent dependencies from the phonological grammar on which they had been trained than those from the grammar on which they had not been trained. A second experiment demonstrated that this facilitative effect was not due to the explicit recognition of the non-adjacent dependencies. In a third experiment, we extended this line of research by evaluating whether more extensive training with the nonword stimuli would lead these nonwords to become lexicalized and, if so, what role non-adjacent phonotactic dependencies would play in lexicalized stimuli. In particular, we asked whether the previous effect of facilitation would now manifest itself as inhibition, presumably due to the competition between lexicalized items sharing non-adjacent phonotactic dependencies. The results add to our understanding of the role that non-adjacent phonotactic dependencies play in the perception of spoken language and to the types of changes that are possible in adult speech perception.