We investigated whether the reported lower incidence of prostate cancer in HIV-positive men is a result of confounding factors or reduced screening. We conducted a cohort study of 17,424 HIV-positive and 182,799 HIV-negative men enrolled in Kaiser Permanente (KP). Subjects were followed from the first KP enrollment after January 01, 1996 for KP Northern California (KPNC) and January 01, 2000 for KP Southern California until the earliest of prostate cancer diagnosis, loss to follow-up, or December 31, 2007. Poisson regression was used to compare cancer rates by HIV status adjusting for age, race, smoking, alcohol/drug abuse, overweight/obesity, and diabetes. For the KPNC subset, we analyzed additional available data by HIV status on testosterone deficiency, and on prostate-specific antigen (PSA) tests as a proxy for cancer screening. The prostate cancer incidence rate was 102/100,000 person-years in HIV-positive men (n = 74 cases) and 131/100,000 person-years in HIV-negative men (n = 1195 cases), with an adjusted rate ratio of 0.73 (95% confidence interval: 0.57 to 0.92; P = 0.008). The reduced risk among HIV-positive men was greater for higher-stage cancers, which are less likely to be biased by screening differences than lower-stage cancers. In the KPNC subset, more HIV-positive (90.8%) than HIV-negative men (86.2%) received a PSA test by age 55 (P < 0.001). Decreased risk for HIV-positive men remained when examined only among those with a previous PSA test, and with adjustment for testosterone deficiency (rate ratio = 0.55; 95% confidence interval: 0.39 to 0.80; P = 0.001). Prostate cancer incidence rates are lower in HIV-positive compared with HIV-negative men, which is not explained by screening differences or the risk factors evaluated.