The nonword phonotactic frequency effect in verbal short-term memory (STM) is characterized by superior recall for nonwords containing familiar as opposed to less familiar phoneme associations. This effect is supposed to reflect the intervention of phonological long-term memory (LTM) in STM. However the lexical or sublexical nature of this LTM support is still debated. We explored this question by using an incidental phonological learning paradigm. We exposed adults and 8-year-olds to an artificial phonotactic grammar that manipulated exclusively sublexical phonological rules. After incidental learning, we administered a nonword repetition STM task, with nonwords being either legal or illegal relative to the artificial phonotactic grammar. STM performance was significantly higher for legal than illegal nonwords, in both children and adults. These results demonstrate that verbal STM is indeed influenced by sublexical phonological knowledge. Moreover, verbal STM appears to reflect very subtle and automatic changes in the organization of the phonological network.