Relational Agents are computational artifacts designed to build and maintain long-term, social-emotional relationships with their users. Central to the notion of relationship is that it is a persistent construct, spanning multiple interactions. Thus, Relational Agents are explicitly designed to remember past history and manage future expectations in their interactions with users. Since face-to-face conversation is the primary context of relationship-building for humans, our work focuses on Relational Agents as a specialized kind of embodied conversational agent (animated humanoid software agents that use speech, gaze, gesture, intonation, and other nonverbal modalities to emulate the experience of human face-to-face conversation). One major achievement was the development of a Relational Agent for health behavior change, specifically in the area of exercise adoption. A study involving 100 subjects interacting with this agent over one month demonstrated that the relational agent was respected more, liked more, and trusted more, and that these ratings were maintained over time (unlike for the non-relational agent, where they were not only significantly lower overall, but also declined over time.) People also expressed significantly greater ratings of perceived caring by the agent, and significantly more desire to keep working with the relational agent after the termination of the study.