Background The incidence of non-melanoma skin cancers (NMSCs), including basal cell (BCC) or squamous cell carcinoma (SCC), is not well documented among HIV-positive (HIV(+)) individuals. Methods We identified 6560 HIV(+) and 36 821 HIV-negative (HIV(-)) non-Hispanic white adults who were enrolled and followed up in Kaiser Permanente Northern California from 1996 to 2008. The first biopsy-proven NMSCs diagnosed during follow-up were identified from pathology records. Poisson models estimated rate ratios that compared HIV(+) (overall and stratified by recent CD4 T-cell counts and serum HIV RNA levels) with HIV(-) subjects and were adjusted for age, sex, smoking history, obesity diagnosis history, and census-based household income. Sensitivity analyses were adjusted for outpatient visits (ie, a proxy for screening). All statistical tests were two-sided. Results The NMSC incidence rate was 1426 and 766 per 100 000 person-years for HIV(+) and HIV(-) individuals, respectively, which corresponds with an adjusted rate ratio of 2.1 (95% confidence interval [CI] = 1.9 to 2.3). Similarly, the adjusted rate ratio for HIV(+) vs HIV(-) subjects was 2.6 (95% CI = 2.1 to 3.2) for SCCs, and it was 2.1 (95% CI = 1.8 to 2.3) for BCCs. There was a statistically significant trend of higher rate ratios with lower recent CD4 counts among HIV(+) subjects compared with HIV(-) subjects for SCCs (P trend < .001). Adjustment for number of outpatient visits did not affect the results. Conclusion HIV(+) subjects had a twofold higher incidence rate of NMSCs compared with HIV(-) subjects. SCCs but not BCCs were associated with immunodeficiency.