This study adds to the limited body of empirical evidence on the effect that legitimacy and deterrence have on compliance behavior. The theoretical models of compliance behavior tested include the basic deterrence model, which focuses on the certainty and severity of sanctions as key determinants of compliance, and models which integrate economic theory with theories from social psychology to account for legitimacy, deterrence, and other motivations expected to influence individuals' decisions whether to comply. Probit and Tobit econometric estimators are used to examine the compliance behavior of 318 Peninsular Malaysian fishermen who face a regulation banning them from fishing in a zone along the coast. The results of the empirical analysis provide additional evidence on the relationship of deterrence and legitimacy to compliance. The findings are also used to draw implications for compliance policy for regulated fisheries.