The tobacco industry contends that the illicit market in Malaysia occupies 62.3% of the total cigarette market. If this is true, Malaysia has one of the largest shares of illicit cigarettes in the world. This study employs a rigorous gap analysis to measure the size of the illicit cigarette trade in Malaysia and compare it with the industry estimates. The researchers found that in 2019, the illicit cigarette market share ranged from 38.2% to 52.5%, depending on assumptions with respect to consumption under-reporting, which is substantially less than the industry estimates. We found that the size of the illicit cigarette market was not driven by higher excise tax: doubling the excise tax rate from RM0.20 to RM0.40 per stick in November 2015 resulted in only a slight increase in the illicit cigarette market share and no increase in the number of illicit cigarettes in the market. Therefore, a reduction in cigarette excise taxes, as suggested by the industry, will not solve the problem of illicit cigarette trade in Malaysia. Instead, the government should ratify the Framework Convention on Tobacco Control’s Protocol to Eliminate Illicit Trade in Tobacco Products and implement the strategies outlined in the protocol.