By adding random noise to individual responses, randomized response techniques (RRTs) are intended to enhance privacy protection and encourage honest disclosure of sensitive information. Empirical findings on their success in doing so are, however, mixed. In nine experiments, we show that the noise introduced by RRTs can make respondents concerned that innocuous responses will be interpreted as admissions, and as a result, yield prevalence estimates that are lower than direct questioning (Studies 1–4, 5A, & 6), less accurate than direct questioning (Studies 1, 3, 4B, & 5A), and even nonsensical (i.e., negative; Studies 3–6). Studies 2A and 2B show that the paradox is eliminated when the target behavior is socially desirable, even when it is merely framed as such. Study 3 shows the paradox is driven by respondents’ concerns over response misinterpretation. A simple modification designed to reduce concerns over response misinterpretation reduces the problem (Studies 4 & 5), particularly when such concerns are heightened (Studies 5 & 6).