Europe's human rights body has called for steps to ensure terror suspects never again "disappear into thin air" from European soil.
CIA flights have landed in European countries, Mr Marty says
The Council of Europe accused states of colluding with the CIA on secret flights transferring prisoners to third countries where they could be tortured.
It urged governments and parliaments in each state to hold their own inquiries.
The US admits renditions have taken place but denies that people sent overseas are subjected to torture.
"People should not be allowed to disappear into thin air, regardless of the crimes of which they accused," said Council of Europe Secretary General Terry Davis.
"If we want to be safe we must be fair.
"The only effective measures against terrorism are those which stop more terrorists than they help to recruit."
Mr Davis said he would be making recommendations to the 46 member states later this year on how to introduce legal safeguards to prevent renditions or other human rights abuses by foreign security agencies.
Earlier this month, Swiss Senator Dick Marty published a report accusing 14 European countries of helping the CIA spin a "spider's web" of disappearances, secret detentions and illegal flights.
The report, based on air traffic logs, satellite images and personal testimonies said there was evidence that Poland and Romania had allowed the CIA to set up secret detention centres on their territory.
Most countries have followed Poland and Romania in denying any wrongdoing.
Critics have pointed out that the report provides circumstantial evidence rather than any hard proof.
But the Parliamentary Assembly of the Council of Europe approved on Tuesday a resolution based on the Marty report, which said it had been "demonstrated incontestably" that secret detentions and illegal flights took place.
It calls for:
- In-depth inquiries at a national level
- A review of the legal framework regulating the intelligence services
- A review of agreements with the US on the use of military infrastructure to ensure they comply with human rights norms
- Efforts to develop "a truly global strategy" against terrorism, with the US
Member states are obliged to respond.
EU Justice Commissioner Franco Frattini, who took part in the debate, also said the flights were a "fact" which the member states had a duty to investigate.
Mr Davis said his own questioning of member states had revealed that no European country currently had adequate legal safeguards to prevent renditions occurring.
He said foreign security agencies were not subject to effective control, and that countries currently had no way of knowing whether aircraft in their airspace were being used for purposes compatible with the European Convention on Human Rights.
He also said there should be exceptions to state immunity in cases of serious abuses of human rights.
A video put together by human rights group Witness, including testimony from men who say they were tortured after being detained by the CIA, was shown on the sidelines of the session in Strasbourg.
Khalid El-Masri, a German citizen, recalls waking up in a prison in Kabul where he was told by an interrogator: "You are in a country with no laws... We can lock you up here for 20 years or bury you, no-one would know."
Binyam Mohammed, an Ethiopian citizen arrested in Pakistan for travelling on a false passport, is still being held at Guantanamo Bay.
In the film, his brother reads from a diary entry which talks about Binyam Mohammed being systematically wounded with a scalpel.
Mr Marty's inquiry will now be continued by a sub-committee of the Parliamentary Assembly.
A parallel inquiry by a European Parliament committee will also continue its work for at least another six months.