When deceiving, one should remember to whom a falsified story was previously told; otherwise he or she may include inconsistencies, and the deception will probably be discovered. Bearing this in mind, we investigated the potential relationship between deception and the ability to remember to whom a piece of information was previously told (i.e., destination memory). Forty-one adults were given a destination memory task in which they had to decide to whom proverbs had previously been told. They were also given a questionnaire about deception (e.g., "I sometimes tell lies if I have to) and a cognitive theory of mind task in which they had to predict the behaviour of protagonists who hold a mistaken belief about the state of the world. Results showed a positive correlation between deception and destination memory (p < .001), a relationship that was further mediated by cognitive theory of mind ability (p < .01). Deception requires monitoring and inferring what targets know, suspect, and believe. This monitoring ability (i.e., cognitive theory of mind) results in better processing of the target and consequently better destination memory. By showing the involvement of deception and theory of mind in destination memory, our findings emphasize the memory variations in social and interpersonal interactions.