Background. Tuberculosis (TB) disease diagnosis in Vietnam relies on symptom screening, chest radiography (CXR), and acid fast bacilli (AFB) sputum smear which have a poor sensitivity in HIV patients. We evaluated the performance of clinical algorithms in screening and diagnosing AFB smear-negative TB in HIV patients. Methods. We enrolled 399 HIV-positive patients seeking care at a HIV clinic in Ho Chi Minh City (HCMC), Vietnam. Participants' demographics, medical history, common TB symptoms, CXR, and laboratory tests were collected. Results. Of 399 HIV patients, 390 had initial AFB-negative smears and 22/390 patients had positive cultures. Symptom screening missed 54% (12/22) of smear-negative pulmonary TB (PTB) cases. Multivariate analysis found CD4+ cell level and CXR were significant PTB predictors. An algorithm combining four TB symptoms and TST presented a high sensitivity (100%), but poorly specific (24%) diagnostic performance for smear-negative PTB. Conclusion. Up to 54% of PTB cases in the HIV-infected population may be missed in the routine screening and diagnostic procedures used in Vietnam. Symptom screening was a poor overall diagnostic measure in detecting smear-negative TB in HIV patients. Our study results suggest that routine sputum cultures should be implemented to achieve a more accurate diagnosis of TB in HIV patients.