Following his triumphant exit from Algiers airport and the accompanying media coverage, Carlos was believed to be hiding somewhere in Algiers.  Shortly after the dramatic conclusion to the OPEC raid, the Austrian government filed a request for his extradition.  They were less than pleased when the Algerian government informed them that, since no extradition treaty existed between the two countries, they were unable to comply with the request.  What the Austrian government did not know was that Carlos had been granted political asylum as part of the deal to release the hostages, which he had readily accepted. 

The French government, who maintained a friendly alliance with Algeria, were also taking a keen interest in his whereabouts, but failed to make an extradition request stating that to do so would only offend the government of their former colony.  This was a curious decision considering that they had written proof, in the form of a letter that Carlos had given to Hernandez Acosta at the time of the latter's release.  The letter was addressed to Carlos's mother and clearly stated that he was responsible for leading the OPEC raid.  For some reason, the French government had originally denied that any such document existed, but later recanted the story.  They were further embarrassed when Scotland Yard experts positively identified the handwriting as being that of the man who called himself Carlos the Jackal.

While many of the world's security agencies, including the CIA, were actively seeking him, Carlos was living in a luxurious villa overlooking Algiers that had been supplied by Algerian President Houari Boumedienne.  Carlos stayed at the villa for two weeks while he waited for Klein to recover in hospital.  During that time, Foreign Minister Bouteflika, the Chief of Police and the head of the Algerian secret service, entertained him at dinner.  To ensure the safety of his guest, Boumedienne also provided bodyguards to protect Carlos twenty-four hours a day.

A week later, when Klein was released from hospital, Carlos and his accomplice flew to Libya where they were greeted warmly by Colonel Qathafi and filmed for television.  Given Libya's refusal to allow Carlos's plane to land during the OPEC hostage drama, Qathafi's expansive attitude was puzzling.  Some years later, an accomplice of Carlos expressed the view that Qathafi had in fact commissioned the OPEC raid and paid Carlos $1 million a year as a reward.  French intelligence later revealed that Qathafi also provided the funds for Carlos's stay in Algeria. 

On February 10, Carlos and Klein flew to Aden in South Yemen for a Popular Front meeting in a private jet supplied by Qathafi.  The meeting was called by Wadi Haddad to review the effectiveness of the OPEC raid.  The meeting lasted for two days during which, Carlos, Klein and Krocher-Tiedemann blamed each other for their failure to carry out the mission according to Haddad's instructions.  Haddad took no part in the heated discussions but took copious notes during the proceedings.  Towards the end of the meeting, Haddad repeatedly questioned Carlos regarding his failure to execute Yamani and Amouzegar as planned. 

When the meeting finished, Carlos and Klein were ordered to attend a Popular Front training camp in Aden while they waited for Haddad's verdict on their actions.  After several days at the camp, Carlos was summoned by Haddad and informed that because he had failed to execute the Arab hostages as planned, he would no longer be welcome as a member of the Popular Front.  In dismissing Carlos Haddad told him: -

"Stars are very bad at following instructions.  You have not followed my instructions.  There is no room for stars in my operational teams.  You can go."

In deference to Carlos, Haddad kept the expulsion secret while his former protégé decided his future.  Years later, Carlos related the incident somewhat differently claiming he had left the Popular Front of his own free will.  His dismissal remained a secret for several months during which time the press reported Carlos was the leader of the 1976 hijacking of an Air France flight to Entebbe, Uganda.  The attack was in fact led by Wilfred Bose who was later killed when Israeli paratroopers launched a successful raid on Entebbe to free the hostages.

In September 1976, Carlos and Klein flew to Belgrade and spent three weeks holidaying in Yugoslavia.  Their movements came to the attention of West German intelligence that in turn notified Belgrade's National Security Council demanding that Carlos and his accomplice be arrested and extradited back to Germany.  The NSC complied and arrested both men.  When Carlos was taken into custody he was in possession of an Algerian diplomatic passport issued under a false name.

After just four days in custody, Carlos was released by order of Marshall Tito because Tito did not want the political embarrassment of having Carlos in Belgrade because French President Valery Giscard d'Estaing was due to arrive for an official visit.  When the United States and German governments criticized Tito's decision they were told that there was no evidence to indicate that Carlos had ever been in Yugoslavia.  Meanwhile Carlos and Klein had been put on a plane to be taken to Baghdad via Damascus.  When the plane arrived in Damascus, they were refused permission to take off again.  Being unarmed, Carlos believed that he and Klein would be shot if they left the plane.  Their fears were confirmed when armed secret service police posing as cleaning staff tried to board the aircraft but failed to gain access when the pilot informed them that the plane constituted foreign territory.

Five hours of intense negotiations followed during which the "cleaners" loosened the plane's wheels to prevent it taking off.  Only after the intervention of two Yugoslav diplomats was the plane released and allowed to fly to Baghdad where the terrorists were supplied with free accommodation, bodyguards and a chauffeured limousine.  Carlos stayed in Iraq for three weeks but was in constant fear of reprisals, especially when he learned that Saudi Arabia had put a million dollar bounty on him.

Carlos eventually chose to settle in Aden, South Yemen where he felt safer.  Again, it was Qathafi who paid his expenses.  During his stay, he spent some time training other terrorist groups, giving them the benefit of his experience, but training others was not what he wanted to do with his life.

From the time of his involvement with the Popular Front, Carlos had thought of only one thing, running his own terrorist organisation.  Several problems had to be solved before he could achieve his goal, mainly where to base his operation and how to raise the funds necessary to run such a group.  Another factor was recruiting a band of loyal followers.  Just as Haddad had taught him, Carlos looked to the West German Revolutionary Cells for an able assistant.  As his first choice, Wilfred Bose, had been killed at Entebbe, Carlos sent for Johannes Weinrich, the man who had assisted in the rocket attack at Orly airport.

Weinrich had previously been arrested for provided the cars used in the Orly attack and was subsequently sent to prison.  However, just eight months into his sentence he was released on probation for health reasons and promptly jumped bail.  He was still on the run when Carlos's offer reached him, which he promptly accepted.  His first task was to recruit Hans-Joachim Klein but after tracking him to a chalet in the Italian Alps, he found a different Klein, one who was disillusioned with the revolutionary cause and opposed to violence to the point that he had tipped off the German authorities about a planned murder of two members of the German Jewish community by the Revolutionary Cell.  Carlos was not impressed that his former accomplice had defected "to the other side."

Shortly after receiving the news, Carlos left Aden for Columbia where he hoped to establish himself as a modern-day Che Guevara.  He quickly found the atmosphere in Latin America less than receptive and returned to the Middle East.

Haddad meanwhile had selected a new team to launch an attack in retaliation for the failed Entebbe raid.  Carlos had hoped that Haddad may have changed his mind and select him to lead the attack but this was not to be.  In place of Carlos, Haddad selected Souhalia Andrawes to lead the attack.  On October 13, 1977, Andrawes and three accomplices hijacked a Lufthansa 737 bound for Somalia and held the eighty-six passengers and crew in exchange for the release of Palestinian and Baader-Meinhof guerrillas held in custody and a $15 million ransom.

In the five days that followed, the planes captain was forced to fly to Italy, Cyprus, Bahrain, Dubai and South Yemen while the passengers sat strapped in their seats doused with flammable liquids.  For the duration of the flight Andrawes strode up and down the aisle yelling abuse, brandishing live grenades, the pins of which she had strapped to her fingers.  When the plane reached South Yemen, Mahmoud, one of Andrawes accomplices accused the pilot of attempting to orchestrate an escape.  The pilot insisted that he had only been talking to Aden airport officials regarding the flight.  Mahmoud then dragged the captain out in front of the passengers and after asking if him if he was guilty or not guilty shot him through the head.  Andrawes, who witnessed the event, burst out laughing, after which the captain's body was left where it lay for some time until it was eventually thrown out onto the tarmac.

The co-pilot was then ordered to fly to Mogadishu in Somalia.  Shortly after the plane landed it was attacked by a West German GSG-9 commando unit.  Using stun grenades supplied by the British SAS, the commandos stormed the plane and killed the terrorists with the exception of Andrawes who had been hiding in a toilet.  When the commandos learned of her hiding place, they fired through the door wounding her in the shoulders and legs.  As was carried away on a stretcher, despite being seriously wounded, she raised her hand in a victory salute and shouted, "the Arabs will win."  

With the failure of yet another of Haddad's plans, Carlos was inspired to push ahead with his own plan of independent action.  In December 1977, accompanied by Libyan intelligence officers, Carlos travelled to Baghdad where he met with Saddam Hussein who was the first to offer his support.  This was an important victory for Carlos as it also guaranteed the support of Iraq's KGB trained secret service, the Al Mukharabat.

His plan received another unexpected boost in March 1978 when Wadi Haddad, aged just forty-nine, died of suspected Leukaemia.  His death cleared the way for Carlos to approach the Middle Eastern states and offer his services as a "terrorist for hire."  For some, the fact that Haddad's death came at a time when Carlos was vying for position, suggests that he may have been a victim of foul play.  The favourite theory is that the Iraqis who openly supported Carlos poisoned Haddad.