Previous research has shown that people sometimes feel uncomfortable in the presence of objects that appear almost, but not quite, human-like. This phenomenon, known as the Uncanny Valley effect, may present an impediment to the widespread acceptance of humanoid robots in everyday life, e.g. as school teachers, nurses, nannies, or clerks. It is therefore important for the field of human-robot interaction to identify ways in which the Uncanny Valley effect can be overcome. The current study was designed to test the hypothesis that sharing a stressful experience with a robot may serve to establish rapport with that specific robot, leading to a boost in people’s willingness to interact with the robot. To this end, we conducted an experiment in which participants underwent a pleasant experience with one virtual agent and a mildly stressful experience with a second virtual agent (the Induction Phase). Next (the Test Phase), they carried out a new series of tasks, before each of which they selected one virtual agent (either one of the two familiar agents or one of two unfamiliar agents) to be their partner for that task. The results indicate that participants chose to partner with the virtual agent with whom they had shared the stressful experience more often than the virtual agent with whom they had shared the pleasant experience, and more often than either of the other two agents. This finding, as well as the results of questionnaires that were administered at the end of the experiment, support the hypothesis that shared stressful experiences help overcome the Uncanny Valley effect.