This paper analyses job seekers' perceptions and their relationship to unemployment outcomes to study heterogeneity and duration-dependence in both perceived and actual job finding. Using longitudinal data from two comprehensive surveys, we document (1) that reported beliefs have strong predictive power of actual job finding, (2) that job seekers are over-optimistic in their beliefs, particularly the long-term unemployed, and (3) that job seekers do not revise their beliefs downward when remaining unemployed. We then develop a reduced-form statistical framework, where we exploit the joint observation of beliefs and ex-post realizations, to disentangle heterogeneity and duration-dependence in true job finding rates while allowing for elicitation errors and systematic biases in beliefs. We find a substantial amount of heterogeneity in true job finding rates, accounting for more than half of the observed decline in job finding rates over the spell of unemployment. Moreover, job seekers' beliefs are systemically biased and under-respond to differences in job finding rates both across job seekers and over the unemployment spell. Finally, we show theoretically and quantify in a calibrated model of job search how these biases in beliefs contribute to the slow exit out of unemployment. The biases jointly explain about 15 percent of the high incidence of long-term unemployment.