We conducted a longitudinal study of tobacco use among adults initiating antiretroviral therapy (ART) in Mbarara, Uganda where 11 % of men and 3 % of women use tobacco according to the 2011 Demographic and Health Survey. In a prospective cohort, self-reported tobacco use was assessed before starting ART and reassessed every 3–4 months. Plasma cotinine, a nicotine metabolite, was measured in a subset of adults pre-ART to verify self-report. Among 496 subjects, 50 (10 %) reported current tobacco use (20 % of men, 6 % of women). Most (53 %) adults with elevated cotinine levels (>15 ng/mL) reported no tobacco use. By 6 months after ART initiation, 33 % of tobacco users had quit (95 % CI 20–46 %). By 5 years, 64 % quit (95 % CI 47–77 %). Self-reported tobacco use among rural Ugandans starting ART was twice as common as among the local background population and use may be underreported. ART initiation could be an opportunity for tobacco cessation interventions.