Vascular disease is a leading cause of death and disability. While it is preventable, little is known about the feasibility or acceptability of implementing interventions to prevent vascular disease in Australian primary health care. We conducted a cluster randomised controlled trial assessing prevention of vascular disease in patients aged 40–65 by providing a lifestyle modification program in general practice. Interviews with 13 general practices in the intervention arm of this trial examined their views on implementing the lifestyle modification program in general practice settings. Qualitative study, involving thematic analysis of semi-structured interviews with 11 general practitioners, four practice nurses and five allied health providers between October 2009 and April 2010. Providing brief lifestyle intervention fitted well with routine health-check consultations; however, acceptance and referral to the program was dependent on the level of facilitation provided by program coordinators. Respondents reported that patients engaged with the advice and strategies provided in the program, which helped them make lifestyle changes. Practice nurse involvement was important to sustaining implementation in general practice, while the lack of referral services for people at risk of developing vascular disease threatens maintenance of lifestyle changes as few respondents thought patients would continue lifestyle changes without long-term follow up. Lifestyle modification programs to prevent vascular disease are feasible in general practice but must be provided in a flexible format, such as being offered out of hours to facilitate uptake, with ongoing support and follow up to assist maintenance. The newly formed Medicare Locals may have an important role in facilitating lifestyle modification programs for this target group.