This study investigates a strategy based on predictability of consecutive sub‐lexical units in learning to segment a continuous speech stream into lexical units using computational modeling and simulations. Lexical segmentation is one of the early challenges during language acquisition, and it has been studied extensively through psycholinguistic experiments as well as computational methods. However, despite strong empirical evidence, the explicit use of predictability of basic sub‐lexical units in models of segmentation is underexplored. This paper presents an incremental computational model of lexical segmentation for exploring the usefulness of predictability for lexical segmentation. We show that the predictability cue is a strong cue for segmentation. Contrary to earlier reports in the literature, the strategy yields state‐of‐the‐art segmentation performance with an incremental computational model that uses only this particular cue in a cognitively plausible setting. The paper also reports an in‐depth analysis of the model, investigating the conditions affecting the usefulness of the strategy.