Virtual humans are animated, lifelike characters capable of free-speech and nonverbal interaction with human users. In this paper, we describe the development of two virtual human characters for teaching the skill of deception detection. An accompanying tutoring system provides solicited hints on what to ask during an interview and unsolicited feedback that identifies properties of truthful and deceptive statements uttered by the characters. We present the results of an experiment comparing use of virtual humans with tutoring against a no-interaction (baseline) condition and a didactic condition. The didactic group viewed a slide show consisting of recorded videos along with descriptions of properties of deception and truth-telling. Results revealed that both groups significantly outperformed the no-interaction control group in a binary decision task to identify truth or deception in video statements. No significant differences were found between the training conditions.