Epstein's agent-based model (ABM) of civil violence has been very popular and successful due to its formulation soundness, simplicity, and explanatory power. Variants of this model have been proposed for the simulation of different types of social conflict phenomena (worker protest, riots, or urban crime) and for investigating the effect of mechanisms that are not considered in the original model. In a previous work, we introduced imprisonment delay, “news impact,” and legitimacy feedback effects in Epstein's ABM of civil violence. In this paper, we focused specifically on improving the formulation of legitimacy feedback. In the model presented herein, legitimacy varies as a function of subindicators identified in theoretical studies on legitimacy measurement. We considered four different functions for expressing the legitimacy—weighted average, geometric mean, exponentially decaying “system support,” and “justification”—and two different feedback mechanisms: homogeneous (global) perceived legitimacy and heterogeneous (agent-dependent) perceived legitimacy. It was found that, for certain combinations of input parameters, the present model produced solutions with an initial period of calm with small bursts of rebellion, followed by a sudden large-scale rebellion after which intermittent bursts of rebellion occur (as in Epstein's model), where legitimacy drops never returning to the initial level. These results provide an alternative explanation of the mechanisms by which apparently stable authoritarian regimes, when facing an unexpected large-scale uprising, respond with repression and afterward struggle with intermittent bursts of rebellion because they are perceived as illegitimate. The present model can also be used to test theories on the aggregation of legitimacy indicators in a global legitimacy score.