Nutri One-on-One was a program with the aim to positively modify medical clinic patients’ nutritional habits and lifestyles through a brief one-on-one health coaching session. Each session was conducted by utilizing motivational interviewing techniques to allow for tailored nutrition education and goal setting. These sessions were followed by a phone call to participants at 1 month following the session. The outcomes assessed were participant perception of achieving personal nutrition and lifestyle goals, retention of knowledge, and participants’ satisfaction with the program. Physicians working in the clinic were assessed for satisfaction with the program. Most of the physicians were generally satisfied with the program and found it to be an asset to their practice. Participants perceived that they achieved their goals, were pleased with the program, and retained knowledge.