Few studies have explicitly identified factors that explain an individual’s willingness to engage in community-based exercise for claudication. Identifying the unique characteristics of those inclined toward physical activity would inform interventions that encourage walking. We examined the utility of behavioral economics-related concepts in understanding walking among Veterans with claudication. Patients who received care at the Michael E. DeBakey Veterans Affairs Medical Center in Houston, Texas, were surveyed on symptom severity, behavioral economics, stress, and depression. The primary outcome was a binary variable measuring current walking for exercise and defined as walking for at least 30 minutes every day. Multivariable logistic regression models were used to identify variables, both clinically and statistically significant, at a p-value < 0.05. Between April 2017 and March 2018, we received 148 (30%) responses. A total of 35% ( n = 51) of respondents indicated that they walked recreationally for exercise compared to 65% ( n = 94) who did not. Characteristics that were significantly associated with walking included regularly saving money (adjusted odds ratio (aOR) = 10.7, p = 0.001), seeking complex problem-solving (aOR = 0.12, p = 0.002), and severe symptoms (aOR = 0.24, p = 0.017). Individuals describing a preference for the future rather than immediate benefit also reported currently walking for exercise. Defining the characteristics of those who exercise may help inform strategies designed to increase walking among those who do not adhere to recommendations.