The purpose of this article is to clarify the relationship between forms of political legitimacy employed by communist regimes in East and Central Europe and subsequent models of revolutionary change in 1989. The conceptual basis of the analysis lies in Max Weber's theoretical framework of legitimacy. The four cases selected for comparison are Bulgaria, Hungary, Poland and Romania. The attempts of de-Stalinization and reformation of these party-state regimes through the introduction of paternalistic and also more goal-oriented measures could not prevent their disintegration in the 1980s and their subsequent collapse in 1989. But, I argue, it was the withdrawal of ideological support by elites that ultimately brought communism to an end. The differences in revolutionary scenarios and transitions to democracy in the four cases indicate the importance of a shift in both rulers and masses towards interest in dialogue and compromise. Hungary and Poland represent the clearest scenarios in which communist parties acted as agents of regime change in a rational-legal direction. The Bulgarian case stands as an intermediary case between these two and Romania. Finally, Romania represents an extreme case of violent revolution and the overthrow of a traditionalist and sultanistic regime and illustrates the difficulties following a complete collapse of political authority.