"If it were confirmed that this is true, we would be faced with extremely serious circumstances, events that are intolerable because they violate rules for treating people, prisoners, in a society and a democratic political and legal system," Interior Minister Jose Antonio Alonso said.
A police investigation of the alleged prisoner transfers at Palma airport on the Mediterranean island of Mallorca has reached a higher level, having been passed on to a judge, he said.
But Defense Minister Jose Bono said Spain has no evidence the CIA used any Spanish airport illegally.
He denied a report in the newspaper El Pais that Spanish intelligence knew of CIA use of the Palma airport earlier this year and urged the CIA to stop the practice.
"We have no proof or even evidence that illicit activities took place, much less ones that might be classified as a crime," Bono told reporters.
He said he had spoken to police chiefs specifically about this issue.
"I am not prepared to point fingers at a government or a country that is an ally, over mere suppositions of which we have no proof," Bono said.
Bartomeu Barcelo, chief prosecutor for the Balearic islands, which include Mallorca, said he had investigated the case in March. He concluded that there was a lack of evidence to press charges and halted the inquiry.
"As we had no material to keep moving ahead, for this reason we agreed to halt" the probe, Barcelo told reporters in Palma.
That investigation began after a newspaper in Palma, Diario de Mallorca, reported a series of suspicious flights arriving and taking off from the city's airports.
Earlier this month, the paper reported that in one case, a CIA flight that left from Palma in January 2004 was involved in the alleged kidnapping of Khaled al-Masri, a Lebanese-born German national. Al-Masri says he was abducted in Macedonia, taken to Afghanistan, beaten and interrogated over his alleged ties to al Qaeda.
El Pais reported that at least 10 CIA flights had used the Palma airport. The flights' destinations included Libya, Morocco, Ireland and Sweden, and their countries of origin included Algeria, Romania and Egypt, it said.
The U.S. government has been criticized by human rights groups for practicing "extraordinary rendition" — sending suspected terrorists to foreign countries, where they are detained, interrogated and subjected to possible ill treatment.