Non-AIDS defining malignancies, including colorectal cancer (CRC), are emerging as significant problems in HIV-infected people. Some data suggest that HIV-positive patients have higher incidence of CRC at younger ages than those who are HIV-negative. This investigation examined CRC rates and screening types and trends between 943 HIV-infected cases and their age, race, and gender matched HIV-negative controls (n = 943) from 1 January 2005 to 31 December 2008 at the Atlanta VA Medical Center. The most common screening type among these patients was fecal occult blood testing (FOBT), but colonoscopies were more common in the controls (16.4% for cases, 27.5% for controls; p < 0.0001). Almost half of all patients included in this analysis did not have any screening for CRC during the four years of follow-up even though average age was 55 years. Fifty-one percent of cases had at least one screening test during follow-up compared to 48% of the controls; 7.6% of the cases had a screening each of the four years compared to only 2.4% of the controls (p < 0.0001). Ten HIV-positive patients were diagnosed with CRC during the study period compared to no CRC diagnoses among controls (p = 0.0015), though there was no difference in the diagnosis of colon polyps (4.6% vs. 5.1%, p = 0.5911). These data also suggest a discrepancy in CRC incidence between race and age groups: 80% of HIV-positive cases diagnosed with CRC during the study were black and two were less than 50 years of age. Future studies will need to address whether different recommendations are needed for screening based on HIV status, younger age, or race.