In the old west, it appears that prostitution was a viable means of making a living, Perfectly legal, or at least not prosecuted.
What was the status of prostitution in more established states in the east? At what point did it become illegal, in the west and why?
In the United States, prostitution has usually been illegal everywhere, with very few exceptions. The bawdy houses you see in movies only existed in mining boom towns and places where enforcement was lax, such as places with large amounts of foreign immigrants. As an example of the laws which were more or less similar throughout the country, here is the relevant act from the Consolidated Laws of Kansas, 1879:
(788) § 50. Sec. 49. The city council shall have power to enact ordinances to restrain, prohibit and suppress tippling shops, billiard tables, — bowling alleys, houses of prostitution and other disorderly houses and practices, games and gambling houses, desecrations of the Sabbath day, commonly called Sunday, and all kinds of public indecencies. No license shall ever be granted for any house of prostitution, or for any gambling house, gambling device, game of chance, or any disorderly house or practice; and no city officer shall accept or receive any hush money, or any money or valuable thing, from any person or persons engaged in any such business or practice, nor grant any immunity or protection against a rigid enforcement of the laws and ordinances enacted to restrain, prohibit and suppress any such business or practice.
As you can see from the law, it was a common practice to bribe officials to overlook the laws.
It never was illegal nationally, and is still legal in some jurisdictions in Nevada. Here in Seattle it was legal until 1911; not coincidentally, women got the franchise in Seattle in 1910. Around the same time the Mann Act made it a federal crime to to 'transport women across state lines for immoral purposes.' However in the pre-FBI days the federal government's power to investigate or enforce these laws was very limited.
It is based on state law not federal. As Tyler said it is legal in a few counties in Nevada, but illegal in other states. It is only legal in a professional manner such as a brothel. As of now no such brothel exists legally in the United States.
