© 2016 Society for Vascular Surgery. Objective Although smoking cessation is a key priority emphasized by professional societies and multidisciplinary consensus guidelines, significant variation exists in the methods and efficacy of smoking cessation treatment practiced by vascular surgeons. We conducted a series of patient, surgeon, and nonpatient stakeholder focus groups to identify important domains for establishment of a successful smoking cessation program. Methods As part of a planning effort for a randomized clinical trial on usual care vs a standardized, evidence-based smoking cessation intervention, our group performed a series of interviews and focus groups. These were four 1-hour interviews, conducted with stakeholders such as tobacco cessation counselors (n = 2), a Quit Line representative (n = 1), and a Vascular Quality Initiative leader (n = 1), as well as two 90-minute, formal, professionally moderated focus groups, one with vascular surgeons (n = 7), and another with patients (n = 4). Transcripts and audio recordings were qualitatively reviewed for themes to establish the most important domains perceived to be associated with a successful smoking cessation program. Results Patients emphasized four domains critical for a successful smoking cessation program: the motivation to quit, an individualized approach, the timing of an intervention, and the tone of the physician who offers counseling. Although surgeons and nonpatient stakeholders also emphasized the importance of a compassionate physician tone, surgeons and nonpatient stakeholders differed from patients in their remaining domains. They emphasized the feasibility of a brief intervention in a busy clinical practice, implementation of the effort, and necessary infrastructure for smoking cessation programs. All focus group participants described a brief, evidence-based smoking cessation intervention as feasible in routine vascular practice. Conclusions Differences in motivation and significance exist for patients, surgeons, and stakeholders when they considered the specific domains most important in building a successful smoking cessation program. Despite these differences, all parties involved agreed that a brief, standardized intervention can be successful delivered in a busy vascular clinic setting.