Do we really encounter as many lies as we think online? The present study examines the possibility of a prevalence paradox, or the discrepancy between one?s beliefs about deception online and actual encounters with deception. This research tests several factors that may influence the prevalence paradox in mediated communication, including characteristics of the user (e.g., experience) and of the communication environment (e.g., synchronicity and evanescence). Participants reported on their beliefs and experiences with deception in email, instant-messaging, blogs, and social networks. Although the results from this study did not support the predicted factors for the prevalence paradox, they did confirm the existence of the paradox in each of the communication environments.