'Prostitution' is neither wholly legal nor wholly illegal in Australia. Some prostitution is legal and other prostitution is not. The rules differ from State to State.
In Victoria the relevant law is the Sex Work Act 1994 (Vic). The term 'sex work' is defined in section 3 of the Act. Note that, even then, not all sex work is necessarily legal or illegal.
In Victoria, it is generally lawful for a person to take money (or money's worth) for sex, as long as it's not as part of a business such as an 'escort agency' or 'brothel' (each term is defined in the Act). However, it is an offence to:
- induce a child to perform sex work: s 5;
- induce a person to perform sex work using violence, intimidation, drugs or fraud: s 8;
- live off the earnings of another person's sex work: s 10;
- loiter near a school or church looking to procure or offer sex work: ss 12 & 13 respectively;
- operate, attend, etc an unlicenced brothel: s 15;
- advertise for people to become sex workers: s 17;
- provide or receive sex work services without a condom etc: s 18A;
- carry on the business of sex work (including an escort agency or brothel) without a licence: s 22 (but certain owner-operators are exempt: s 23);
- many other things.
In conclusion, a person paying rent in the form of sex is likely to be legal, but they would have to use a condom, take steps to reduce the risk of sexually transmitted diseases, etc. Advertising 'come live here in exchange for sex' would, however, be illegal.