Our research aims at developing interactive, social agents that can coach people to learn new tasks, skills, and habits. In this paper, we focus on coaching sedentary, overweight individuals to exercise regularly. We employ adaptive goal setting in which the coach generates, tracks, and revises personalized exercise goals for a trainee. The goals become incrementally more difficult as the trainee progresses through the training program. Our approach is model-based the coach maintains a parameterized model of the trainee’s aerobic capability that drives its expectation of the trainee’s performance. The model is continually revised based on interactions with the trainee. The coach is embodied in a smartphone application which serves as a medium for coach-trainee interaction. We show that our approach can adapt the trainee program not only to several trainees with different capabilities but also to how a trainee’s capability improves as they begin to exercise more. Experts rate the goals selected by the coach better than other plausible goals, demonstrating that our approach is effective.