Non-melanoma skin cancer (NMSC) is the most common malignancy, whose public health significance is often unrecognized. This analysis has two objectives: first, to provide up-to-date incidence estimates by sex, age group, histological type, and body site; and second, to study the impact of skin cancer screening. The impact of screening on NMSC incidence in Schleswig-Holstein, Germany, is analyzed by comparing four time periods of different screening settings (no screening (1998-2000), pilot project (Skin Cancer Research to Provide Evidence for Effectiveness of Screening in Northern Germany, SCREEN, 2003-2004), after SCREEN (2004-2008), and nation-wide skin cancer screening (2008-2010)) to a reference region (Saarland, Germany). Age-standardized (Europe) NMSC incidence was 119/100,000 for women and 145/100,000 for men in the most recent screening period in Schleswig-Holstein (2008-2010). During implementation of SCREEN (2003-2004), incidence increased from 81.5/100,000 to 111.5/100,000 (1998-2000) by 47% for women and 34% for men. All age groups in women were affected by the increase, but increases for men were mostly limited to the older age groups. Incidence in Saarland first increased slowly, but increased steeply with the introduction of the nation-wide skin cancer screening in 2008 (+47% for women and +40% for men, reference 2004-2008). Observed changes are most likely attributed to screening activities.