Background: Exposure to carbon monoxide (CO) remains a leading occupational hazard in firefighters, but cigarette and waterpipe smoking likely contributes to the other sources of CO in such workers. The aim of this study was to estimate the contribution of self-reported active cigarette smoking, waterpipe use, and potential job-related sources of CO to the level of exhaled CO in firefighters. Methods: We surveyed the personnel of 18 fire stations (N = 842), median age 28 years, who participated at an annual screening not timed to coincide with recent firefighting. We surveyed smoking and waterpipe history, exposure to secondhand smoke (SHS), use of coal for health and biomass for cooking and time since last exposure to firefighting in the workplace. We measured exhaled CO with an instantaneous reading device (piCO Smokerlyzer). We used multivariable regression models to test the association of time since last smoked cigarette (≤12 h) and waterpipe (≤12 h) and time since last fire (≤6 h) with exhaled CO. Results: In analysis limited to men (93.5% of all surveyed), 42% were daily cigarette; 1% were waterpipe smokers; 94% were exposed to SHS, 29% used coal for heating and 4% used biomass for cooking. The median CO was 4 (interquartile range 3;8) ppm. Age (beta 0.74 per 10 years, p < 0.001), use of biomass fuel for cooking (beta 1.38, p = 0.05), cigarette smoked in the last 12 h (beta 8.22, p < 0.001), waterpipe smoked in the last 12 h (beta 23.10, p < 0.001) were statistically associated with CO, but not time since last fire (≤6 h) (beta 4.12, p = 0.12). There was a significant interaction between older age and firefighting for exhaled CO (p = 0.03). Conclusions: Cigarette and recent waterpipe smoking are associated with increased exhaled CO in firefighters. Firefighting itself was a less potent contributor to exhaled CO when measured at an annual screening, but an age interaction was manifested.