Little is known about how HIV affects undocumented immigrants despite social and structural factors that may place them at risk of poor HIV outcomes. Our understanding of the clinical epidemiology of HIV-infected undocumented immigrants is limited by the challenges of determining undocumented immigration status in large data sets. We developed an algorithm to predict undocumented status using social security number (SSN) and insurance data. We retrospectively applied this algorithm to a cohort of HIV-infected adults receiving care at a large urban healthcare system who attended at least one HIV-related outpatient visit from 1997 to 2013, classifying patients as "screened undocumented" or "documented". We then reviewed the medical records of screened undocumented patients, classifying those whose records contained evidence of undocumented status as "undocumented per medical chart" (charted undocumented). Bivariate measures of association were used to identify demographic and clinical characteristics associated with undocumented immigrant status. Of 7593 patients, 205 (2.7%) were classified as undocumented by the algorithm. Compared to documented patients, undocumented patients were younger at entry to care (mean 38.5 years vs. 40.6 years, p < 0.05), less likely to be female (33.2% vs. 43.1%, p < 0.01), less likely to report injection drug use as their primary HIV risk factor (3.4% vs. 18.0%, p < 0.001), and had lower median CD4 count at entry to care (288 vs. 339 cells/mm, p < 0.01). After medical record review, we re-classified 104 patients (50.7%) as charted undocumented. Demographic and clinical characteristics of charted undocumented did not differ substantially from screened undocumented. Our algorithm allowed us to identify and clinically characterize undocumented immigrants within an HIV-infected population, though it overestimated the prevalence of patients who were undocumented.