Can even a handful of newly learned words help to find further word candidates in a novel spoken language? This study shows that the statistical segmentation of words from speech stream by adults is facilitated by the presence of known words in the stream. This facilitatory effect is immediate as the known words were acquired only minutes before the onset of the speech stream. Our results demonstrate an interplay between top-down lexical segmentation and bottom-up statistical learning, in line with infant research suggesting that integration of multiple cues facilitates early language learning. The ability to simultaneously benefit from both types of word segmentation cues appears to be present through adulthood and can thus contribute to second language learning.