Introduction: Although research suggests gender differences in patterns of tobacco use, whether gender moderates concurrent use of tobacco and other substances remains unclear. In some parts of Africa and the Middle East, tobacco is often accompanied with khat (Catha edulis), a widely used substance in these regions. The concurrent use of tobacco and khat may represent a public health burden spreading to other countries in Europe and North America. Method: A total of 189 participants (69 women) khat users and smokers in Yemen were asked to complete questionnaires that focused on patterns of khat and tobacco use. Chi-square tests, analyses of variance, and correlational analyses were conducted. Results: Reported frequency and intensity of khat and tobacco use were greater among men than in women. Also, reported number of cigarettes smoked during a khat session was higher among men than among women, whereas frequency of waterpipe use during the session was greater among women than among men. Smoking status (daily or occasional) was positively associated with khat use in women only. Age of onset of khat use was inversely related to the number of cigarettes smoked during a khat session and with intensity of khat chewing. The majority of participants reported that they had thought about and have attempted to quit khat and tobacco use. Conclusions: The results provide evidence for gender differences in patterns of concurrent use of tobacco and khat. Identifying determinants of tobacco and khat use may be useful in reducing the risk of their negative health outcomes.