The purpose of the present study was to examine the relative effectiveness of two different ways of operationalizing a mastery experience in an e-mail based fitness walking program. Mastery experiences are considered the best way to increase exercise self-efficacy (Bandura, 1997), which is strongly associated with regular physical activity, but little research has systematically explored how effective mastery experiences can be developed. Fifty-nine sedentary adult women were randomly assigned to a mastery experience group (n=29) that operationalized mastery experiences in a manner consistent with Bandura's social cognitive theory, or to a standard care group (n=30) that operationalized mastery experiences in a manner consistent with standard care. Both intervention conditions received the same physical activity prescription and were designed to promote equivalent levels of contact with the experimenter over the 12-week program. The effects of the program were examined on overall adherence to the program, one-mile walk test times, estimated VO2max, social cognitive outcomes, and program evaluation ratings. Both the mastery experience group and the standard care group had similar levels of adherence to the program. The mastery experience group demonstrated a significantly greater improvement in one-mile walk test time than the standard care group. Although the mastery experience group also showed a larger increase in estimated VO2max than the standard care group, this difference did not reach significance. The mastery experience group had significantly greater increases in goal-setting relative to the standard care group, but the intervention did not show any differences between the two groups on three measures of self-efficacy. In program evaluation ratings, the mastery experience group demonstrated greater satisfaction with the program than the standard care group.