But the ruling by a lower court has now been suspended by the Bangladesh Supreme Court, which is also considering whether it will hear an appeal by the government against the ruling.
The law minister said the Supreme Court order meant that , as before, prostitution was generally forbidden but would be tolerated in some areas designated for that purpose.
The decision to legalise prostitution, taken by the High Court, had angered some Islamic groups which argued that prostitution was banned in most Muslim countries.
The court order followed the eviction of hundreds of sex workers from three brothels last July.
Dancing and singing, sex workers marched through the streets of Dhaka in an attempt to mobilise public opinion in their favour.
The BBC's David Chazan says they handed out pamphlets to surprised bystanders, explaining that if they were not allowed to work, they would not be able to feed their children.
“We were not born as prostitutes, but circumstances forced us into this life,” said Momtaz Begum.
One women's rights organisation, Sanghati, said many of the sex workers were forced into the streets after their eviction.
“I move from one part of the city to another every day and spend nights at the parks,” one of the evicted women, Anjum, said.
The women are being supported by health workers who say it is easier to check the spread of sexually transmitted diseases when the sex trade is out in the open.
In its ruling, the Bangladesh High Court said: “The right to livelihood of sex workers is enforceable as a fundamental right.”
The judgement was welcomed by human rights activists and lawyers and it made Bangladesh one of the few Islamic countries which do not ban prostitution.
“It was a very courageous decision,” Dr Monica Beg of the aid agency, Care, told the BBC.
“I think it is a historical decision, because we have never … heard that this kind of decision has come from any high court, especially in this region,” she said.
But the decision is opposed by many in the country and several of the sex workers said they were still being harassed by police.
Our correspondent says some lawyers believe that if the government is allowed to appeal, the supreme court could overturn the ruling.