Objectives: Previous state interagency collaborations have led to successful tobacco cessation initiatives. The objective of this study was to assess the roles and interaction of state Medicaid and public health agency efforts to support tobacco cessation for low-income Medicaid beneficiaries. Methods: We interviewed Medicaid and state public health agency officials in 8 states in September and October 2015 about collaborations in policy development and implementation for Medicaid tobacco cessation, including Medicaid coverage policies, quitlines, and monitoring. Results: Collaboration between Medicaid and public health agencies was limited. Smoking cessation quitlines were the most common area of collaboration cited. Public health officials were typically not involved in developing Medicaid coverage policies. States covered a range of US Food and Drug Administration-approved tobacco cessation medications, but 7 of the 8 states imposed limitations, such as charging copayments or requiring previous authorization. States generally lacked data to monitor implementation of tobacco cessation efforts and had little ability to determine the effectiveness of their policies. Conclusions: To strengthen efforts to reduce smoking and tobacco-related health burdens and to monitor the effectiveness of policies and programs, Medicaid and public health agencies should prioritize tobacco cessation and develop and analyze data about smoking and cessation efforts among Medicaid beneficiaries. Recent multistate initiatives from the Centers for Disease Control and Prevention and the Centers for Medicare & Medicaid Services seek to promote stronger collaborations in clinical prevention activities, including tobacco cessation.