Basically alter the long history of humankind, or at least the parts where Christianity (among other religions) condemned prostitution. Prostitution was condemned and then criminalized for reasons which should be apparent to anyone who has paid attention for the past hundreds of years.
The quasi-legal status of prostitution suits most people, except for the few johns and prostitutes that are caught in enforcement nets (usually through deliberate entrapment in the former case, and the latter is almost never acted upon without some other reason to target the woman). It is also highly unlikely to find any society which would actually enforce its anti-prostitution laws in a consistent and universal manner, so punishments are usually doled out to those without the connections to operate outside the law.
The likely trend in the future will be the quasi-legal status where prostitutes are unpunished, but their clients are punished and scorned. It really comes down to the moral values of a society, and as much as the current regime likes to pretend it is liberal and free, it is actually strict in its own ways about who can do what and who is allowed to feel what way.
The best case scenario is that all men collectively agree to never pay for sex, and the sordid trade withers away... but that didn't work for slavery (isn't working for slavery, really), and the trajectory of this society is entirely opposite of what should happen.
There's nothing wrong with prostitution if it's between consenting adults. Contrary to popular belief, women can and do choose this line of work out of their own free will. There's nothing sordid about it if there's no force and no drugs involved. So far, the American model of criminalizing prostitutes as well as johns has proven ineffective and there have been indications that the Swedish model, which criminalizes clients only, doesn't work either:
Police in Gothenburg have confirmed that sex trafficking in the city has developed into a full-blown slave trade - but that they lack the resources to do anything about it.
Gothenburg police busted a large Romanian pimping network in 2011, but it wasn't long before new brothel-keepers from various countries took over. Now the problem is back with a vengeance, with police admitting they lack the resources to address it - and are thus forced to ignore the reports.
"We haven't worked with the issue at all for a year now," Stefan Adamsson, police officer in the Gothenburg trafficking unit, told The Local. "We would need to be three times as many police to be able to do anything about it."
Newspaper Expressen reported earlier this week that human traffickers had gone from "just" selling sex to selling women as lifelong slaves.
The newspaper's sources said the cost for a slave - "for life" - is €2,000 ($2680). For 700 kronor ($100) one can rent a couple of girls for a day, for cooking, cleaning, or anything else. "Do what you like with them," one seller reportedly said.
Source. Here's another interesting
article.
But not to derail this thread and make it all political, I shall return to the topic at hand. For one, you have to somehow undermine the argument that illegalization is the best way to combat sex trafficking. You'd also have to keep the Woman's Christian Temperance Union from getting political influence somehow. Getting conservatives to turn a blind eye instead of going all brimstone and whatnot would help, so the ultra-religious nuts needs to be kept out of politics. In short, the US needs to become way more secular.
Also, two key federal policies hastened the end of red-light districts: the passage of the Mann Act, or “white slave traffic act,” created the first federal law around prostitution in 1910; and at the start of the first world war, a Navy decree demanded the closure of all sex-related businesses in close range of military bases, under the premise of “protecting” enlisted men from sexually transmitted infections. Based on fear and opportunity, Storyville was closed.
The first would have to be altered toward combating the causes of prostitution and at combating trafficking and slavery rather than the prostitutes and their clients. As for the second, you'd need to change the navy's mindset into thinking that navy crews need to vent their sexual frustration, and that the navy or an affiliated third party should make condoms available somehow.