A stream of research examining the effect of punishment on conformity indicates that punishment can backfire and lead to suboptimal social outcomes. We examine whether this effect is due to a lack of perceived legitimacy of rule enforcement, enabling agents to justify selfish behavior. We address the question of punishment legitimacy by shedding light upon the importance of social norms and their interplay with punishment. People are often presented with incomplete norm information: either about what most others do (empirical) or what most others deem appropriate (normative). We show that in isolation, neither punishment nor empirical/normative information increase prosocial behavior. In turn, we find that prosociality significantly increases when normative information and punishment are combined, but only when compliance is relatively cheap. When compliance is more expensive, we find that the combination of punishment and empirical information about others' conformity can have detrimental effects. In additional experiments, we explain how this negative effect is due, at least for some individuals, to punishment not being perceived as justified. Our results have important implications for researchers and practitioners alike.