In two artificial language learning experiments, we investigated the impact of attention load on segmenting speech through two sublexical cues: transitional probabilities (TPs) and coarticulation. In Experiment 1, we observed that coarticulation processing was resilient to high attention load, whereas TP computation was penalized in a graded manner. In Experiment 2, we showed that encouraging participants to actively search for “word” candidates enhanced overall performance but was not sufficient to preclude the impairment of statistically driven segmentation by attention load. As long as attentional resources were depleted, independently of their intention to find these “words,” participants segmented only TP words with the highest TPs, not TP words with lower TPs. Attention load thus has a graded and differential impact on the relative weighting of the cues in speech segmentation, even when only sublexical cues are available in the signal.