BACKGROUND: Sex workers are disproportionately affected by HIV compared with the general population. Most studies of HIV risk among sex workers have focused on individual-level risk factors, with few studies assessing potential structural determinants of HIV risk. In this Article, we examine whether criminal laws around sex work are associated with HIV prevalence among female sex workers. METHOD: We estimate cross-sectional, ecological regression models with data from 27 European countries on HIV prevalence among sex workers from the European Centre for Disease Control; sex-work legislation from the US State Department's Country Reports on Human Rights Practices and country-specific legal documents; the rule of law and gross-domestic product per capita, adjusted for purchasing power, from the World Bank; and the prevalence of injecting drug use among sex workers. Although data from two countries include male sex workers, the numbers are so small that the findings here essentially pertain to prevalence in female sex workers. FINDINGS: Countries that have legalised some aspects of sex work (n=17) have significantly lower HIV prevalence among sex workers than countries that criminalise all aspects of sex work (n=10; β=-2·09, 95% CI -0·80 to -3·37; p=0·003), even after controlling for the level of economic development (β=-1·86; p=0·038) and the proportion of sex workers who are injecting drug users (-1·93; p=0·026). We found that the relation between sex work policy and HIV among sex workers might be partly moderated by the effectiveness and fairness of enforcement, suggesting legalisation of some aspects of sex work could reduce HIV among sex workers to the greatest extent in countries where enforcement is fair and effective. INTERPRETATION: Our findings suggest that the legalisation of some aspects of sex work might help reduce HIV prevalence in this high-risk group, particularly in countries where the judiciary is effective and fair. FUNDING: European Centre for Disease Prevention and Control.