It should be legal, since it's not a government's job to be the Moral Police. Not unless you also ban infidelity, failing to tithe to your church, etc.
This is where conservatives in the US political system are wrong. They always say we should follow the Constitution and limit government involvement, yet they're the same people who want to ban all of the things they don't like. I don't see prostitution written anywhere in the Constitution. You either want to give people the freedom to make their own mistakes, or you want to run an authoritarian society. I would always choose the former.