There is a great deal of controversy over Holocaust denial in modern societies. Still, the general agreement seems to be that it is not only irrational but also inhuman to try to refute or soften the horrors of the death camps. However, there is far less consensus in societies considered as liberal democracies over whether the state should respond to Holocaust denial, especially in its verbal form, via legal means, that is, by punishing it with the means of criminal law. Most European countries do have such laws, although some of them implemented them only recently. Furthermore, there seems to be no relationship between the existence of such laws in the state and the quality of democracy and freedom of speech in it. This paper examines two puzzles emerging from such a state of art. Firstly, at the theoretical level, what is the danger, if any, entailed in Holocaust denial, for democracies? Could it help a new totalitarian regime to emerge, as some scholars seem to argue? Moreover, ‘who’ is in danger – the individual, the society, the democratic regime, or a particular minority; and ‘how’ can this danger come into being? Secondly, at the empirical level, why do some democracies enact laws against Holocaust denial? Building on major interpretations of totalitarianism and the Holocaust, with the help of review of contemporary arguments for and against restricting Holocaust denials by the means of law, this paper aims to address these questions and find out what are the consequences of (not) restricting Holocaust denial by laws in the long run of development of European (democratic) societies. Through a comparative analysis of parliamentary discourse in three Central European democracies, it demonstrates that while a mixture of justifications in favor of banning Holocaust denial is presented to audiences in democracies, ranging from collective responsibility and preservation of human dignity of the victims to the need to secure freedom and prevent such horrors from happening again, the overwhelming majority of them rests upon the belief that truth (in this case, the Holocaust) can be cemented and separated from politics. The paper concludes that while separating truth from politics in the case of Holocaust denial is a legitimate political decision, it bears consequences for the strength of remembrance of this part of human history.