In order to retrieve Carlos from his new hiding place, the French government knew that their only option was to convince the Sudanese to give him up. After inviting the heads of the two Sudanese intelligence sections to Paris, the DST and the DGSE offered to sell them much needed communications equipment and even supplied them with satellite pictures of their enemies positions. The courtship seemed to be going well when the CIA received a tip that gave the exact location of Carlos. The French immediately sent Phillipe Rondot, the intelligence officer who had previously tracked Carlos down to Algiers and Colombia, to Sudan to confirm if the information was correct. On his arrival he met with the Sudanese authorities that promptly denied any knowledge of the terrorists presence. Rondot decided to find out for himself and lost no time in locating Carlos and was able to take photographs of him with a concealed camera as proof of his whereabouts.
Faced with this new undeniable evidence, the Sudanese authorities agreed that Carlos was a guest in their country and the negotiations to extract him from his hideout began. To help sweeten the deal, the French Minister of the Interior, Charles Pasqua invited Sheik Hassan al-Turabi to Paris. In the first round of talks, al-Turabi made it clear that to give up a man that was a guest in his country amounted to treachery. Pasqua countered by offering to approach the World Bank and the International Monetary Fund, on Sudan's behalf, to secure loans to eventually erase Sudan's foreign debt. Although Pasqua did not have the authority to back up his offers, the discussions opened the way for future negotiations.
Further pressure was applied to the Sudanese government when the Egyptian secret service also tracked Carlos to Khartoum. With multiple countries now seeking Carlos's expulsion, the Sudanese were being pressured into a decision, give up Carlos or be denounced for sheltering terrorists.
The final straw came when a secret video of Carlos at a party was shown to al-Turabi. He was already aware of his guest's reputation for partying, drinking and carousing with women and as a devout Moslem it offended him. Finally in August 1994, al-Turabi advised the French that they were going to give Carlos up because as al-Turabi explained to one of his senior officials:
"We welcomed him as a combatant, someone who fought for the Palestinian cause, for noble causes. Now he's a hoodlum, his behaviour is shameful. He drinks and goes out with women so much that I don't know if he's a Moslem. Given that his presence has become a real danger we are going to hand him over. We have no regrets. Because of his behaviour, we are absolved from blame."
Al-Turabi made one final stipulation; he insisted that Carlos was not to be harmed during his capture, as he did not want any reprisals against his decision.
On Saturday, August 13, Carlos was admitted to the Ibn Khaldoun hospital in Khartoum for a minor operation to correct a low sperm count. Since his daughter had left with Kopp, Carlos had been anxious to father another child with his new wife but had been unable to. Following the procedure, Carlos was recovering in his room under the protection of his bodyguards, when a Sudanese policeman entered his room and advised him that his department had uncovered a plot to kill him. Carlos was then offered a transfer to a military hospital so he could be better protected while he fully recovered. Carlos agreed and under an armed escort, he and his wife were taken from the hospital, but rather than being taken to a military hospital, the pair were taken firstly to the Sudanese State Security headquarters before being driven to a villa in a suburb called Taif, close to the home of Sheik al-Turabi. Any objections that Carlos had regarding the change of plans were quickly dispelled when he was told it was for his own protection.
Carlos was less than impressed when they arrived at the newest destination. The villa was in poor condition and had very few appointments. After their first night in the villa, the couple were anxious to go home but soon realised that they would have to spend a second day there. In an attempt to make life more bearable, Carlos sent his wife back to their home to pick-up some of their needed possessions. When she had not returned by 10pm, Carlos went to bed.
At approximately 3am, he was woken by a group of men pinning him to the bed. Before he could resist, he was handcuffed hand and foot and had a thin hood pulled over his head. A doctor then stepped forward and injected him in the thigh with a hypodermic containing a tranquilliser. A stretcher was produced and Carlos was bundled unceremoniously into a van that drove him to Khartoum airport where an executive jet was standing by.
By the time the jet had cleared Sudanese airspace, Carlos realised that his captors were French, what he did not know was that he was in the hands of the DST. He was then placed in a sack and bound tightly, with only his hooded head protruding. Six-and-a half hours later, the jet landed at Villacoublay military airport outside Paris where he was handed over to another DST team and driven to their Paris headquarters. As soon as he was unloaded and taken inside the building, Judge Jean-Louis Bruguiere issued Carlos with a national arrest warrant for the murder of two DST agents at Rue Toullier in 1979. By issuing such a warrant, the French government avoided the cumbersome process of applying to Interpol for an extradition order.
To confirm the prisoner's identity, his fingerprints were taken and compared with those lifted from drinking glasses at Rue Toullier and the thumbprints from the letter of demand that was sent to Gaston Deferre. Satisfied that they had the right man, the DST then escorted Carlos to La Sante, a maximum-security prison. The official announcement of Carlos's capture differed somewhat from the truth, when Charles Pasqua announced that the Sudanese government had assisted in the service of the arrest warrant and the DST had then captured Carlos when he landed at Villacoublay airfield, when they had in fact violated several International laws by taking Carlos out of Sudan by force.