We explore the ways long-term learning improves short-term memory search. In varied mapping (VM) targets on one trial are foils on the next and vice versa; in consistent mapping (CM), targets and foils never change roles. CM training leads to highly efficient search. Two mechanisms may underlie the effect: ‘Item Learning’ in which each item comes to be associated to the appropriate ‘target’ or ‘foil’ response, and ‘Category Learning’ in which all items come to be coded as members of a category. Categorical varied mapping (CV) allows these to be distinguished: Members of a category have the same role on each trial, but the role switches between trials. Using arbitrary pictures as stimuli we show that, during early stages of practice, item learning and not category learning governs responding in both CM and CV. Using already learned categories of letters and numbers we demonstrate use of category learning.