OBJECTIVE: New tools, including light-emitting diode (LED) fluorescence microscopy and the molecular assay Xpert MTB/RIF, offer increased sensitivity for tuberculosis (TB) in persons with HIV but come with higher costs. Using operational data from rural Malawi, we explored the potential cost-effectiveness of on-demand screening for TB in low-income countries of Sub-Saharan Africa. DESIGN AND METHODS: Costs were empirically collected in 4 clinics and in 1 hospital using a microcosting approach, through direct interview and observation from the national TB program perspective. Using decision analysis, newly diagnosed persons with HIV were modeled as being screened by 1 of the 3 strategies: Xpert, LED, or standard of care (ie, at the discretion of the treating physician). RESULTS: Cost-effectiveness of TB screening among persons newly diagnosed with HIV was largely determined by 2 factors: prevalence of active TB among patients newly diagnosed with HIV and volume of testing. In facilities screening at least 50 people with a 6.5% prevalence of TB, or at least 500 people with a 2.5% TB prevalence, Xpert is likely to be cost-effective. At lower prevalence-including that observed in Malawi-LED microscopy may be the preferred strategy, whereas in settings of lower TB prevalence or small numbers of eligible patients, no screening may be reasonable (such that resources can be deployed elsewhere). CONCLUSIONS: TB screening at the point of HIV diagnosis may be cost-effective in low-income countries of Sub-Saharan Africa, but only if a relatively large population with high prevalence of TB can be identified for screening.