With health care services struggling with high volume of patients with concerning skin lesions, nurses’ contribution to early recognition of skin cancer could be valuable. The aim was to study whether specially trained nurses are capable of identifying suspicious potentially malignant skin lesions as reliably as an experienced dermatologist. Patients who scheduled an appointment with a counseling nurse had a total body skin examination, performed independently first by a nurse and immediately thereafter by a dermatologist who prescribed further procedures, if warranted. Skin cancer risk factors, the agreement between nurses’ and dermatologist’s clinical judgements, and predictive factors for referrals were investigated. Histopathological data were collected from medical records. 300 patients (77% women) with the mean age of 56 years (range 19­­-91) were included. Nurses’ clinical suspicion rate (referral to a physician’s examination) was 52% (n = 156). The dermatologist recommended further management to 54 patients (18%), most of whom (n = 39) warranted a skin biopsy. The nurses were able to recognise 89% of those to whom the dermatologist prescribed further procedures. In multivariate analysis, nurse’s referral was the only significant predictor of dermatologist’s recommendation for further management (OR 8.2, 95% CI 3.07-21.91, p < 0.001). Ten patients were diagnosed histopathologically with skin cancer (nine basal cell carcinomas, two cutaneous squamous cell carcinomas and one melanoma), yielding a detection rate of 3.3%. For the dermatologist, the positive predictive value for skin cancers was 31%. It can be concluded that specially educated nurses can reliably screen skin cancer and save medical resources.