Examination of search strategies has tended to focus on choices determined by decision makers' personal preferences among relevant cues, and not on learning cue-criterion relationships. We present an empirical and rational analysis of cue search for environments with objective criteria. In such environments, cues can be evaluated on the basis of three properties: validity (the probability that a cue identifies the correct choice if cue values differ between alternatives); discrimination rate (the proportion of occasions on which a cue has differing values); and success (the expected proportion of correct choices when only that cue can be used). Our experiments show that though there is a high degree of individual variability, success is a key determinant of search. Furthermore, a rational analysis demonstrates why success-directed search is the most adaptive strategy in many circumstances. Copyright © 2004 John Wiley & Sons, Ltd.