States try to combat sex trafficking through both the criminalization of buying sex and by entirely legalizing or regulating the market for prostitution. Proponents of criminalization argue that this approach leads to less acceptance of prostitution, creating a smaller sex market, and reducing the inflow of trafficked victims. Few studies examine if prostitution laws are associated with attitudes toward prostitution. We assess attitudes in eight European countries, using newly collected survey data. This is one of few studies comparing attitudes across different prostitution regimes. Citizens in countries where the purchase of sex is criminalized are less tolerant toward the buying of sex compared to citizens living in countries where the purchase of sex is legalized. Also, people viewing gender equality as important are less accepting of the purchase in countries where buying sex is prohibited, but more accepting in countries where buying sex and running a brothel are legal.