Background: The use of Anabolic-Androgenic Steroids (AAS) has been associated with increased aggressiveness and violent behavior. We therefore investigated the proposed correlation between the use of AAS and criminality while controlling for important socio-economics covariates and for psychiatric comorbidity. Methods: The primary endpoints were prison sentences, and time to first prison sentence. A retrospective matched cohort study design consisting of 545 males, who tested positive for AAS in Danish gyms during the period January 3, 2006 to January 31, 2017. They were matched with 5450 randomly chosen male controls. Data were cross-referenced with national register information on education, employment status, substance abuse and psychiatric comorbidity. In addition, 638 males sanctioned because they rejected to participate in the doping control and 6380 controls were used as a replication cohort. Results: Already at baseline, 20.6% of the AAS users had a previous prison sentence whereas the rate was 3.7% in the control cohort (p < 0.0001). During the follow-up period the cumulative prevalence increased to 29.5% and 4.9%, respectively (unadjusted HR 9.15, 95% CI 6.33–13.20). The associations remained highly significant after controlling for socio-economic factors, drug abuse and psychiatric comorbidity. The results could be replicated in a similar cohort. Conclusion: Our study shows that AAS users have a 9-fold increased risk of being convicted of a crime compared to matched controls, randomly chosen from the general population. This association could not be explained by common socioeconomic factors or by psychiatric comorbidity.