For almost a decade, ‘public legitimacy’ has remained largely unaddressed in empirical international relations (IR) analyses of international legalization. Yet, this concept has behavioral consequences. IR scholars for long assume that a belief in the legitimacy of a norm may be one reason for a ‘compliance pull’ on the international stage. The present study addresses this gap. It suggests a sociological conception of legalization observable in mass media debates and encompassing law’s ‘public legitimacy’, understood as the congruence between legal regulations and discursive practices to that effect that these rules are also accepted by the larger public. This conception is illustrated in European and US newspaper reporting about military interventions in the post-Cold War era (1990-2005). Based on a large-n media analysis, the study not only concludes that an ‘international rule of law’ frame is heavily diffused across the communicative practices of European and US public spheres. It also shows that two legal norms in particular – human rights and United Nations (UN) multilateralism – generate a shared sense of ‘public legitimacy’ across the six countries analyzed.