In the Sternberg item recognition task and its variants, an individual's mean reaction time increases with the number of items to be retained in the memory set. An increase in reaction time has also been seen when a secondary task was added. The usual interpretation for this increased reaction time is that adding cognitive load makes tasks more difficult. In a series of three experiments, we manipulated cognitive load through increases in the memory set or through a second task. In each experiment, high cognitive load was associated with higher mean response times but a reduced slope, based on the target position in a series of probes. Thus, in a Sternberg task with multiple word targets and multiple word probes, participants searched more efficiently per probe under high load than under low load. This pattern was replicated with the addition of a working memory task requiring participants to calculate a cumulative price based on the price per target word item. By considering both initial response times and reaction time slopes in large memory sets, this study provides a challenge to the traditional interpretation of cognitive load effects on search performance.