Workplace health programs have demonstrated improvements in a number of risk factors for chronic disease. However, there has been little investigation of participant characteristics that may be associated with change in risk factors during such programs. The aim of this paper is to identify participant characteristics associated with improved waist circumference (WC) following participation in a four-month, pedometer-based, physical activity, workplace health program. 762 adults employed in primarily sedentary occupations and voluntarily enrolled in a four-month workplace program aimed at increasing physical activity were recruited from ten Australian worksites in 2008. Seventy-nine percent returned at the end of the health program. Data included demographic, behavioural, anthropometric and biomedical measurements. WC change (before versus after) was assessed by multivariable linear and logistic regression analyses. Seven groupings of potential associated variables from baseline were sequentially added to build progressively larger regression models. Greater improvement in WC during the program was associated with having completed tertiary education, consuming two or less standard alcoholic beverages in one occasion in the twelve months prior to baseline, undertaking less baseline weekend sitting time and lower baseline total cholesterol. A greater WC at baseline was strongly associated with a greater improvement in WC. A sub-analysis in participants with a 'high-risk' baseline WC revealed that younger age, enrolling for reasons other than appearance, undertaking less weekend sitting time at baseline, eating two or more pieces of fruit per day at baseline, higher baseline physical functioning and lower baseline body mass index were associated with greater odds of moving to 'low risk' WC at the end of the program. While employees with 'high-risk' WC at baseline experienced the greatest improvements in WC, the other variables associated with greater WC improvement were generally indicators of better baseline health. These results indicate that employees who started with better health, potentially due to lifestyle or recent behavioural changes, were more likely to respond positively to the program. Future health program initiators should think innovatively to encourage all enrolees along the health spectrum to achieve a successful outcome.