I believe the state law is that in any county where the population is under 400,000 residents, prostitution is legal, which rules out the main large cities in Nevada. I live in neighboring Utah, so I learn some interesting factoids about our neighbor once in a while.
Oddly enough, if you read the link that you posted, you'd learn that contrary to your statement, prostitution is illegal in Reno and Las Vegas, and in fact in great swathes of Nevada (in particular, it's illegal in the areas where most NV residents live).
If comedy central has ever taught me anything, it is that there is still illegal prostitution in Reno, Nevada. ;)