BACKGROUND: Health behaviors related to diet, tobacco usage, physical activity, medication adherence, and alcohol use are highly determinative of risk for developing cardiovascular disease. This paper describes a study protocol to evaluate a problem-solving intervention that aims to help patients at risk for developing cardiovascular disease address barriers to adopting positive health behaviors in order to reduce cardiovascular risk. METHODS: Eligible patients are adults enrolled in Veterans Affairs (VA) health care who have not experienced a cardiovascular event but are at elevated risk based on their Framingham Risk Score (FRS). Participants in this two-site study are randomized to either the intervention or care as usual, with a target of 400 participants. The study intervention, Healthy Living Problem-Solving (HELPS), consists of six group sessions conducted approximately monthly interspersed with individualized coaching calls to help participants apply problem-solving principles. The primary outcome is FRS, analyzed at the beginning and end of the study intervention (6months). Participants also complete measures of physical activity, caloric intake, self-efficacy, group cohesion, problem-solving capacities, and demographic characteristics. CONCLUSION: Results of this trial will inform behavioral interventions to change health behaviors in those at risk for cardiovascular disease and other health conditions. TRIAL REGISTRATION: ClinicalTrials.gov identifier NCT01838226.