© 2018, The Author(s). Cigarette smoking alters the oral microbiome; however, the effect of alternative tobacco products remains unclear. Middle Eastern tobacco products like dokha and shisha, are becoming globally widespread. We tested for the first time in a Middle Eastern population the hypothesis that different tobacco products impact the oral microbiome. The oral microbiome of 330 subjects from the United Arab Emirates Healthy Future Study was assessed by amplifying the bacterial 16S rRNA gene from mouthwash samples. Tobacco consumption was assessed using a structured questionnaire and further validated by urine cotinine levels. Oral microbiome overall structure and specific taxon abundances were compared, using PERMANOVA and DESeq analyses respectively. Our results show that overall microbial composition differs between smokers and nonsmokers (p = 0.0001). Use of cigarettes (p = 0.001) and dokha (p = 0.042) were associated with overall microbiome structure, while shisha use was not (p = 0.62). The abundance of multiple genera were significantly altered (enriched/depleted) in cigarette smokers; however, only Actinobacillus, Porphyromonas, Lautropia and Bifidobacterium abundances were significantly changed in dokha users whereas no genera were significantly altered in shisha smokers. For the first time, we show that smoking dokha is associated to oral microbiome dysbiosis, suggesting that it could have similar effects as smoking cigarettes on oral health.