Standard search theory assumes that individuals know, with certainty, how they compare to competing searchers in terms of ability. In contrast, we hypothesize that searchers are uncertain about relative ability, with important implications for search behavior. We test our hypotheses in a laboratory experiment. The first main finding is that people are substantially uncertain about whether they are a type with a high or low probability of success, determined by being above or below the median in terms of ability. Self-confidence, defined as an individual's self-assessed probability of being a high type, is too high (above zero) for many low types, and too low (below 1) for many high types. Second, people update beliefs based on search outcomes. Self-confidence increases or decreases in the right direction, but is less sensitive to new information than predicted by Bayes' rule. Third, updating affects future search decisions: people are less likely to search as confidence about being a high type falls. Fourth, some search too little, and others search too much, due to wrong beliefs. Fifth, at the end of the experiment a substantial fraction turn down the chance to learn their exact rank. These are overwhelmingly those with low ability, suggesting an aversion to learning that one is one of the worst performers. Given that people are uncertain even in the simple setting of our experiment, our evidence strongly suggests that uncertainty about ability is relevant in more complex, real-world search settings, including search for a job or search for a mate. Focusing on the case of job search, we discuss how our findings can provide a new explanation for various important stylized facts from field evidence.