Health coaching can improve lifestyle behaviors known to prevent or manage chronic conditions such as diabetes. However, little is known about the patient experience with telephonic coaching programs in real-world care settings. We examined patient satisfaction, patient’s perceived success in achieving program goals, and the patient-level correlates of these outcomes in a voluntary telephonic coaching program at a large integrated health care delivery system in northern California. Kaiser Permanente Northern California patients who participated in a telephonic coaching program in 2011 were sent a cross-sectional survey about their satisfaction with health coaching and perceived success with program goals. We examined associations with patient characteristics. The survey response rate was 34%; analyses were based on the 32% who completed the survey. Of those who had completed 2 or more sessions (n = 232 [52%]), most reported being satisfied (70%) or neutral (20%) with the program, and 71% would recommend health coaching. Healthy weight, healthful eating, and physical activity were the most common topics discussed (88%). Adjusting for demographic characteristics, 73% of those who had 2 or more sessions reported that health coaching helped achieve their weight-related goal. Outcomes were positively correlated with patient activation but not consistently correlated with patient demographic characteristics. Levels of satisfaction and perceived success with telephonic health coaching provided by a health plan were high and positively correlated with the number of sessions completed and patient activation. Voluntary telephonic health coaching programs should promote retention and assess patients’ activation levels.