This paper represents an effort to investigate the impact of perceived new media credibility on citizens’ online political efficacy (OPE) in new democracies. Unlike their counterparts in mature democracies and outright authoritarian states, citizens of new democracies face the challenge to reconcile their democratic present with the authoritarian past. Their online political behaviors therefore are likely to be shaped by the interaction between democratic realities and authoritarian legacies or memories. The current study argues that in new democracies, the relationship between credibility of new media and OPE is contingent upon citizens’ authoritarian experience. Since authoritarian experience delivers a sense of relative acquisition through a comparison mechanism, it is expected to play a positive role in moderating the association between credibility of new media and OPE. We test the proposition by studying a sample of Taiwanese residents interviewed during the 2015 Taiwan Communication Survey (TCS). Our empirical analyses produce strong supportive evidence for the positive conditioning effect of authoritarian experience and the result is robust to different model specifications and alternative measures of authoritarian experience.