Abstract Background Although dental care settings provide an exceptional opportunity to reach smokers and provide brief cessation advice and treatment to reduce oral and other tobacco-related health conditions, dental care providers demonstrate limited adherence to evidence-based guidelines for treatment of tobacco use and dependence. Methods/Design Guided by a multi-level, conceptual framework that emphasizes changes in provider beliefs and organizational characteristics as drivers of improvement in tobacco treatment delivery, the current protocol will use a cluster, randomized design and multiple data sources (patient exit interviews, provider surveys, site observations, chart audits, and semi-structured provider interviews) to study the process of implementing clinical practice guidelines for treating tobacco dependence in 18 public dental care clinics in New York City. The specific aims of this comparative-effectiveness research trial are to: compare the effectiveness of three promising strategies for implementation of tobacco use treatment guidelines—staff training and current best practices (CBP), CBP + provider performance feedback (PF), and CBP + PF + provider reimbursement for delivery of tobacco cessation treatment (pay-for-performance, or P4P); examine potential theory-driven mechanisms hypothesized to explain the comparative effectiveness of three strategies for implementation; and identify baseline organizational factors that influence the implementation of evidence-based tobacco use treatment practices in dental clinics. The primary outcome is change in providers’ tobacco treatment practices and the secondary outcomes are cost per quit, use of tobacco cessation treatments, quit attempts, and smoking abstinence. Discussion We hypothesize that the value of these promising implementation strategies is additive and that incorporating all three strategies (CBP, PF, and P4P) will be superior to CBP alone and CBP + PF in improving delivery of cessation assistance to smokers. The findings will improve knowledge pertinent to the implementation, dissemination, and sustained utilization of evidence-based tobacco use treatment in dental practices. Trial registration NCT01615237 .