Background: The uptake of intensified active TB case-finding among HIV-infected patients using symptom screening is not well understood. We evaluated the rate and completeness of each interim step in the TB pulmonary "diagnostic cascade" to understand real-world barriers to active TB case detection. Methods: We conducted a cohort analysis of new, antiretroviral therapy-naive, HIV-infected patients who attended a large HIV clinic in Mbarara, Uganda (March 1, 2012 - September 30, 2013). We used medical records to extract date of completion of each step in the diagnostic cascade: symptom screen, order, collection, processing, and result. Factors associated with lack of sputum order were evaluated using multivariate Poisson regression and chart review of 50 screen-positive patients. Results: Of 2613 patients, 2439 (93%) were screened for TB and 682 (28%) screened positive. Only 90 (13.2%) had a sputum order. Of this group, 83% completed the diagnostic cascade, 13% were diagnosed with TB, and 50% had a sputum result within 1 day of their visit. Sputum ordering was associated with WHO stage 3 or 4 HIV disease and greater number of symptoms. The main identifiable reasons for lack of sputum order in chart review were treatment of presumed malaria (51%) or bacterial infection (43%). Conclusions: The majority of newly enrolled HIV-infected patients who screened positive for suspected TB did not have a sputum order, and those who did were more likely to have more symptoms and advanced HIV disease. Further evaluation of provider behavior in the management of screen-positive patients could improve active TB case detection rates.