Screening by whole-body clinical skin examination may improve early diagnosis of melanoma and reduce mortality, but objective scientific evidence of this is lacking. As part of a randomized controlled trial of population screening for melanoma in Queensland, Australia, the authors assessed the validity of self-reported history of whole-body skin examination and factors associated with accuracy of recall among 2,704 participants in 2001. Approximately half of the participants were known to have undergone whole-body skin examination within the past 3 years at skin screening clinics conducted as part of the randomized trial. All positive and negative self-reports were compared with screening clinic records. Where possible, reports of skin examinations conducted outside the clinics were compared with private medical records. The validity of self-reports of whole-body skin examination in the past 3 years was high: Concordance between self-reports and medical records was 93.7%, sensitivity was 92.0%, and specificity was 96.3%. Concordance was lower (74.3%) for self-reports of examinations conducted in the past 12 months, and there was evidence of “telescoping” in recall for this more recent time frame. In multivariate analysis, women and younger participants more accurately recalled their history of skin examinations. Participants with a history of melanoma did not differ from other participants in their accuracy of recall.