We explored the factors influencing voluntary counseling and testing (VCT) utilization among tuberculosis patients attending two referral hospitals in Cambodia. We conducted face-to-face interviews using a structured questionnaire. We compared HIV/AIDS knowledge, HIV testing attitudes, risks for exposure to HIV, and AIDS stigma between VCT users and non-users. Compared to VCT non-users, VCT users had significantly higher risks for HIV and were more likely to have used condoms. Regarding stigma, VCT non-users demonstrated significantly greater AIDS stigmatizing beliefs compared to VCT users. To increase VCT utilization among TB patients, we need effective strategies to reduce AIDS stigma among them. Moreover, initiation of routine HIV testing in TB facilities might be another effective solution.