Objective To compare the performance of the new WHO (2007) diagnostic algorithm for pulmonary tuberculosis (PTB) in high HIV prevalent settings (WHO07) to the WHO 2003 guidelines used by the Ugandan National Tuberculosis Program (UgWHO03). Methods A prospective observational cohort design was used at Reach Out Mbuya Parish HIV/AIDS Initiative, an urban slum community-based AIDS Service Organisation (ASO) and Kayunga Rural District Government Hospital. Newly diagnosed and enrolled HIV-infected patients were assessed for PTB. Research staff interviewed patients and staff and observed operational constraints. Results WHO07 reduced the time to diagnosis of smear-negative PTB with increased sensitivity compared with the UgWHO03 at both sites. Time to diagnosis of smear-negative PTB was significantly shorter at the urban ASO than at the rural ASO (12.4 vs. 28.5 days, P = 0.003). Diagnostic specificity and sensitivity [95% confidence intervals (CIs)] for smear-negative PTB were higher at the rural hospital compared with the urban ASO: [98% (93-100%) vs. 86% (77-92%), P = 0.001] and [95% (72-100%) vs. 90% (54-99%), P > 0.05], respectively. Common barriers to implementation of algorithms included failure by patients to attend follow-up appointments and poor adherence by healthcare workers to algorithms. Conclusion At both sites, WHO07 expedited diagnosis of smear-negative PTB with increased diagnostic accuracy compared with the UgWHO03. The WHO07 expedited diagnosis more at the urban ASO but with more diagnostic accuracy at the rural hospital. Barriers to implementation should be taken into account when operationalising these guidelines for TB diagnosis in resource-limited settings.