Virtual coaches have the potential to address the low adherence common to eHealth applications for behavior change by, for example, providing motivational support. However, given the multitude of factors affecting users’ attitudes toward virtual coaches, more insights are needed on how such virtual coaches can be designed to affect these attitudes in a specific use context positively. Especially valuable are insights that are based on users interacting with such a virtual coach for longer. We thus conducted a study in which more than 500 smokers interacted with the text-based virtual coach Sam in five sessions. In each session, Sam assigned smokers a new preparatory activity for quitting smoking and provided motivational support for doing the activity. Based on a mixed-methods analysis of users’ willingness to continue working and their relationship with Sam, we obtained eight themes for users’ attitudes toward Sam. These themes relate to whether Sam is seen as human or artificial, specific characteristics of Sam (e.g., caring character), the interaction with Sam, and the relationship with Sam. We used these themes to formulate literature-based recommendations to guide designers of virtual coaches for behavior change. For example, letting the virtual coach get to know users and disclose more information about itself may improve its relationship with users.