Background: Early detection and treatment of cryptococcal antigen (CrAg) may decrease morbidity and mortality from cryptococcal meningitis. Based on World Health Organization guidelines, South Africa recommends screening all HIV-infected people with CD4 <100/mm3 for CrAg. The prevalence of cryptococcal infections across varying CD4 counts has not been reported at initial HIV diagnosis. We sought to assess the prevalence of cryptococcal infections, stratified by CD4 count, among newly diagnosed HIV-infected adults attending outpatient clinics in Durban. Methodology: We enrolled newly-diagnosed HIV-infected adults into a prospective study between October 2011 and January 2013. Participants were recruited from 4 outpatient sites offering HIV testing services, including an urban hospital, a peri-urban hospital, and 2 municipal peri-urban primary health clinics. Eligible participants were ≥18 years old, newly-diagnosed with HIV, not receiving antiretroviral therapy, and initially seeking outpatient care for a variety of complaints. Participants provided a urine specimen in a sterile container that was stored in a -20 °C freezer for later testing. We performed CrAg testing with the rapid CrAg lateral flow assay (Immy Inc., Norman, OK; estimated 98% sensitivity on urine specimens) according to the manufacturer’s specifications. We assessed CrAg prevalence for a difference above/below CD4 100/mm3 (primary analysis), and above/below CD4 200/mm3 (secondary analysis). Results: Among 773 participants, mean age was 34.4 years, and 41% were female. Overall CrAg prevalence was 10.1% (95% CI 8.0-12.2%), and was not significantly associated with age or gender. CD4 count was available for 660 (85%) participants; median CD4 count was 210/mm3 [Interquartile Range (IQR) 80-358/mm3]. Participants with CD4 >100/mm3 had an estimated CrAg prevalence of 9.9% (95% CI 7.2-12.6%), which was not significantly difference from those with CD4 ≤100/mm3 (8.7%; 95% CI 4.7-12.6%). Similarly, participants with CD4 >200/mm3 had an estimated CrAg prevalence of 14.7% (95% CI 10.5-19.0%), which was significantly higher than those with a CD4 ≤200/mm3 (7.5%; 95% CI 4.6-10.4%). Median CD4 count was 249/mm3 (IQR 83-445/mm3) among CrAg-positive participants, and 203/mm3 (IQR 80-352/mm3) among CrAg-negative participants. Conclusions: Prevalence of cryptococcal infection at the time of HIV diagnosis is high in Durban. Our data suggest there is little difference in those designated as high risk versus low risk for cryptococcal infection using the current CD4 count screening criteria. Therefore, the screening recommendation should be reexamined as it misses many cryptococcus-infected people.