Background HIV testing efficiency could be improved by focusing on high yield populations and identifying types of health facilities where people with undiagnosed HIV infection are more likely to attend. Methods A retrospective cohort analysis of data collected during an integrated TB/HIV active case-finding intervention in Western Kenya. Data were analyzed from health facilities’ registers on individuals who reported TB-suggestive symptoms between 1 July and 31 December 2018 and who had an HIV test result within one month following symptom screening. We used logistic regression with general estimating equations adjusting for sub-county level data to identify health facility-level predictors of new HIV diagnoses. Results Of 11,376 adults with presumptive TB identified in 143 health facilities, 1038 (9%) tested HIV positive. The median HIV positivity per health facility was 6% (IQR = 2–15%). Patients with TB symptoms were over three times as likely to have a new HIV diagnosis in private not-for-profit facilities compared to those in government facilities (adjusted odds ratio (aOR) 3.40; 95% CI = 1.96–5.90). Patients tested in hospitals were over two times as likely to have a new HIV diagnosis as those tested in smaller facilities (i.e., health centers and dispensaries) (aOR 2.26; 95% CI = 1.60–3.21). Conclusion Individuals with presumptive TB who attended larger health facilities and private not-for-profit facilities had a higher likelihood of being newly diagnosed with HIV. Strengthening HIV services at these facilities and outreach to populations that use them could help to close the HIV diagnosis gap.