Again and again over the past two years, a military coalition led by Saudi Arabia and backed by the United States has claimed it won decisive victories that drove al-Qaida militants from their strongholds across Yemen and shattered their ability to attack the West.

Here’s what the victors did not disclose: many of their conquests came without firing a shot.

That’s because the coalition cut secret deals with al-Qaida fighters, paying some to leave key cities and towns and letting others retreat with weapons, equipment and wads of looted cash, an investigation by The Associated Press has found. Hundreds more were recruited to join the coalition itself.

These compromises and alliances have allowed al-Qaida militants to survive to fight another day — and risk strengthening the most dangerous branch of the terror network that carried out the 9/11 attacks. Key participants in the pacts said the U.S. was aware of the arrangements and held off on any drone strikes.

The deals uncovered by the AP reflect the contradictory interests of the two wars being waged simultaneously in this southwestern corner of the Arabian Peninsula.

In one conflict, the U.S. is working with its Arab allies — particularly the United Arab Emirates — with the aim of eliminating the branch of extremists known as al-Qaida in the Arabian Peninsula, or AQAP. But the larger mission is to win the civil war against the Houthis, Iranian-backed Shiite rebels. And in that fight, al-Qaida militants are effectively on the same side as the Saudi-led coalition — and, by extension, the United States.

“Elements of the U.S. military are clearly aware that much of what the U.S. is doing in Yemen is aiding AQAP and there is much angst about that,” said Michael Horton, a fellow at the Jamestown Foundation, a U.S. analysis group that tracks terrorism.

“However, supporting the UAE and the Kingdom of Saudi Arabia against what the U.S. views as Iranian expansionism takes priority over battling AQAP and even stabilizing Yemen,” Horton said.

The AP’s findings are based on reporting in Yemen and interviews with two dozen officials, including Yemeni security officers, militia commanders, tribal mediators and four members of al-Qaida’s branch. All but a few of those sources spoke on condition of anonymity, fearing reprisals. Emirati-backed factions, like most armed groups in Yemen, have been accused of abducting or killing their critics.

Coalition-backed militias actively recruit al-Qaida militants, or those who were recently members, because they’re considered exceptional fighters, the AP found.

The coalition forces are comprised of a dizzying mix of militias, factions, tribal warlords and tribes with very local interests. And AQAP militants are intertwined with many of them.

One Yemeni commander who was put on the U.S. terrorism list for al-Qaida ties last year continues to receive money from the UAE to run his militia, his own aide told the AP. Another commander, recently granted $12 million for his fighting force by Yemen’s president, has a known al-Qaida figure as his closest aide.

In one case, a tribal mediator who brokered a deal between the Emiratis and al-Qaida even gave the extremists a farewell dinner.

Horton said much of the war on al-Qaida by the UAE and its allied militias is a “farce.”

“It is now almost impossible to untangle who is AQAP and who is not since so many deals and alliances have been made,” he said.

The U.S. has sent billions of dollars in weapons to the coalition to fight the Iran-backed Houthis. U.S. advisers also give the coalition intelligence used in targeting on-the-ground adversaries in Yemen, and American jets provide air-to-air refueling for coalition war planes. The U.S. does not fund the coalition, however, and there is no evidence that American money went to AQAP militants.

The U.S. is aware of an al-Qaida presence among the anti-Houthi ranks, a senior American official told reporters in Cairo earlier this year. Because coalition members back militias with hard-line Islamic commanders, “it’s very, very easy for al-Qaida to insinuate itself into the mix,” the official said, speaking on condition of anonymity under the terms of the briefing.

More recently, the Pentagon vigorously denied any complicity with al-Qaida militants.

“Since the beginning of 2017, we have conducted more than 140 strikes to remove key AQAP leaders and disrupt its ability to use ungoverned spaces to recruit, train and plan operations against the U.S. and our partners across the region,” Navy Cmdr. Sean Robertson, a Pentagon spokesman, wrote in an email to the AP.

An Emirati government spokesman did not reply to questions from the AP.

But on Monday, Emirati Minister of State for Foreign Affairs Anwar Gargash tweeted that the UAE-backed counter-terrorism strategy is working. He said it had “removed” thousands of militants and deprived them of safe havens.

AQAP is “at its weakest since 2012,” he wrote, adding that the UAE and its allies “have all lost troops in the fight.”

Coalition spokesman Col. Turki al-Malki on Monday said the AP's findings were "incorrect" and "not based on convincing facts and evidence."

"The coalition is waging a war on terrorist organizations in Yemen, like al-Qaida, the Islamic State group and the Houthi militia," he said. "It continues to carry our joint operations with its friends and brothers to dismantle these groups' capabilities."

The coalition began fighting in Yemen in 2015 after the Houthis overran the north, including the capital, Sanaa. The UAE and Saudi Arabia are determined to stop what they consider a move by their nemesis, Iran, to take over Yemen, and their professed aim is to restore the internationally recognized government of President Abed Rabbo Mansour Hadi.

Al-Qaida is leveraging the chaos to its advantage.

“The United States is certainly in a bind in Yemen,” said Katherine Zimmerman, a research fellow at the American Enterprise Institute. “It doesn’t make sense that the United States has identified al-Qaida as a threat, but that we have common interests inside of Yemen and that, in some places, it looks like we’re looking the other way.”

Within this complicated conflict, al-Qaida says its numbers — which U.S. officials have estimated at 6,000 to 8,000 members — are rising.

An al-Qaida commander who helps organize deployments told the AP that the front lines against the Houthis provide fertile ground to recruit new members.

“Meaning, if we send 20, we come back with 100,” he said.

The well-known commander communicated with AP via a secure messaging app on condition of anonymity because he had no authorization from the group to talk to the news media.

___

A FAREWELL DINNER FOR AL-QAIDA

In February, Emirati troops and their Yemeni militia allies flashed victory signs to TV cameras as they declared the recapture of al-Said, a district of villages running through the mountainous province of Shabwa — an area al-Qaida had largely dominated for nearly three years.

It was painted as a crowning victory in a months-long offensive, Operation Swift Sword, that the Emirati ambassador to Washington, Yousef al-Otaiba, had proclaimed would “disrupt the terrorist organization’s network and degrade its ability to conduct future attacks.”

The Pentagon, which assisted with a small number of troops, echoed that promise, saying the mission would weaken the group’s ability to use Yemen as a base.

But weeks before those forces’ entry, a string of pickup trucks mounted with machine guns and loaded with masked al-Qaida militants drove out of al-Said unmolested, according to a tribal mediator involved in the deal for their withdrawal.

The U.S. has killed al-Qaida’s top leaders in a drone strike campaign that accelerated in recent years. But in this victory — as in the others touted by the coalition — the mediator said armed U.S. drones were absent, despite the large, obvious convoy.

Under the terms of the deal, the coalition promised al-Qaida members it would pay them to leave, according to Awad al-Dahboul, the province’s security chief. His account was confirmed by the mediator and two Yemeni government officials.

Al-Dahboul said about 200 al-Qaida members received payments. He did not learn the exact amounts, but said he knew that 100,000 Saudi rials ($26,000) were paid to one al-Qaida commander — in the presence of Emiratis.

Under the accord, thousands of local tribal fighters were to be enlisted in the UAE-funded Shabwa Elite Force militia. For every 1,000 fighters, 50 to 70 would be al-Qaida members, the mediator and two officials said.

Saleh bin Farid al-Awlaqi, a pro-Emirati tribal leader who was the founder of one Elite Force branch, denied any agreements were made. He said he and others enticed young al-Qaida members in Shabwa to defect, which weakened the group, forcing it to withdraw on its own. He said about 150 fighters who defected were allowed into the Elite Force, but only after they underwent a “repentance” program.

The clearing of al-Qaida from Shabwa and other provinces did not completely take place without fighting. Clashes erupted in some villages, usually with al-Qaida remnants that refused to play ball.

One former al-Qaida member told the AP that he and his comrades turned down an offer of money from the Emiratis. In response, he said, an Elite Force squad besieged them in the town of Hawta until they withdrew.

Overall, deals that took place during both the Obama and Trump administrations have secured al-Qaida militants’ withdrawal from multiple major towns and cities that the group seized in 2015, the AP found. The earliest pact, in the spring of 2016, allowed thousands of al-Qaida fighters to pull out of Mukalla, Yemen’s fifth-largest city and a major port on the Arabian Sea.

The militants were guaranteed a safe route out and allowed to keep weapons and cash looted from the city — up to $100 million by some estimates — according to five sources, including military, security and government officials.

“Coalition fighter jets and U.S. drones were idle,” said a senior tribal leader who saw the convoy leaving. “I was wondering why they didn’t strike them.”

A tribal sheikh shuttled between AQAP leaders in Mukalla and Emirati officials in Aden to seal the deal, according to a former senior Yemeni commander.

Coalition-backed forces moved in two days later, announcing that hundreds of militants were killed and hailing the capture as “part of joint international efforts to defeat the terrorist organizations in Yemen.”

No witnesses reported militants killed, however. “We woke up one day and al-Qaida had vanished without a fight,” a local journalist said, speaking to AP on condition of anonymity for fear of reprisals.

Soon after, another accord was struck for AQAP to pull out of six towns in the province of Abyan, including its capital, Zinjibar, according to five tribal mediators involved in the negotiations.

Again, the central provision was that the coalition and U.S. drones cease all bombings as AQAP pulled out with its weapons, the mediators said.

The agreement also included a provision that 10,000 local tribesmen — including 250 al-Qaida militants — be incorporated into the Security Belt, the UAE-backed Yemeni force in the area, four Yemeni officials said.

For nearly a week in May 2016, the militants departed in trucks. One of the mediators told the AP that he threw the last of the departing fighters a farewell dinner among his olive and lemon orchards when they stopped at his farm to pay their respects.

Another mediator, Tarek al-Fadhli, a former jihadi once trained by al-Qaida leader Osama bin Laden, said he was in touch with officials at the U.S. Embassy and in the Saudi-led coalition, keeping them updated on the withdrawal.

“When the last one left, we called the coalition to say they are gone,” he said.

___

‘WE WILL UNITE WITH THE DEVIL’

To think of al-Qaida as an international terror group is to miss its other reality. For many Yemenis, it is simply another faction on the ground — a very effective one, well-armed and battle-hardened.

Its members are not shadowy strangers. Over the years, AQAP has woven itself into society by building ties with tribes, buying loyalties and marrying into major families.

Power players often see it as a useful tool.

Hadi’s predecessor as Yemen’s president, long-ruling strongman Ali Abdullah Saleh, set the model. He took billions in U.S. aid to combat al-Qaida after the 9/11 attacks, even as he recruited its militants to fight his rivals. Hadi’s current vice president, Ali Mohsen al-Ahmar, a military chief for decades, also has been accused of enlisting jihadis.

In that light, it would almost be more startling if the militants were not involved against the Houthis, especially since al-Qaida militants are extremist Sunnis seeking the defeat of the Shiite rebels.

Al-Qaida militants are present on all major front lines fighting the rebels, Khaled Baterfi, a senior leader in the group, said in a previously unpublished 2015 interview with a local journalist obtained by the AP.

Last month, Baterfi said in a Q&A session distributed by al-Qaida that “those at the front lines for sure know of our participation, which is either actual fighting with our brothers in Yemen or supporting them with weapons.”

Al-Qaida has reduced attacks against Hadi’s and Emirati-linked forces because assailing them would benefit the Houthis, Baterfi said.

The branch is following guidance from al-Qaida’s worldwide leader, Ayman al-Zawahri, to focus on fighting the rebels, another top AQAP member said in written answers to the AP.

In some places, militants join battles independently. But in many cases, militia commanders from the ultraconservative Salafi sect and the Muslim Brotherhood bring them directly into their ranks, where they benefit from coalition funding, the AP found. The Brotherhood’s Yemen branch is a powerful hard-line Islamic political organization allied to Hadi.

Two of the four main coalition-backed commanders along the Red Sea coast are allies of al-Qaida, the al-Qaida member said. The coalition has made major advances on the coast, and is currently battling for the port of Hodeida.

Video footage shot by the AP in January 2017 showed a coalition-backed unit advancing on Mocha, part of an eventually successful campaign to recapture the Red Sea town.

Some of the unit’s fighters were openly al-Qaida, wearing Afghan-style garb and carrying weapons with the group’s logo. As they climbed behind machine guns in pick-up trucks, explosions from coalition airstrikes could be seen on the horizon.

An AQAP member interviewed in person by the AP in May viewed the video and confirmed the fighters belonged to his group. His affiliation is known from his past involvement in AQAP’s rule over a southern city.

The impact of the intertwining of al-Qaida fighters with the coalition campaign is clearest in Taiz, Yemen’s largest city and center of one of the war’s longest running battles.

In the central highlands, Taiz is Yemen’s cultural capital, a historic source of poets and writers and educated technocrats. In 2015, the Houthis laid siege to the city, occupying surrounding mountain ranges, sealing the entrances and shelling it mercilessly.

Taiz residents rose up to fight back, and coalition cash and weapons poured in — as did al-Qaida and Islamic State militants, all aimed at the same enemy.

One liberal activist took up arms alongside other men from his neighborhood to defend the city, and they found themselves fighting side by side with al-Qaida members.

“There is no filtering in the war. We are all together,” said the activist, who spoke on condition of anonymity. He said commanders received weapons and other aid from the coalition and distributed it to all the fighters, including al-Qaida militants.

Abdel-Sattar al-Shamiri, a former adviser to Taiz’s governor, said he recognized al-Qaida’s presence from the start and told commanders not to recruit members.

“Their response was, ‘We will unite with the devil in the face of Houthis,’” al-Shamiri said.

He said he warned coalition officials, who were “upset” but took no action.

“Taiz is in danger,” al-Shamiri said. “We will get rid of the Houthis and we will be stuck with terrorist groups.”

The activist and officials in the city said one of the main recruiters of al-Qaida fighters is Adnan Rouzek, a Salafi member tapped by Hadi to be a top military commander.

Rouzek’s militia became notorious for kidnappings and street killings, with one online video showing its masked members shooting a kneeling, blindfolded man. Its videos feature al-Qaida-style anthems and banners.

Rouzek’s top aide was a senior al-Qaida figure who escaped from a prison in Aden in 2008 along with other AQAP detainees, according to a Yemeni security official. Multiple photos seen by the AP show Rouzek with known al-Qaida commanders in recent years.

In November, Hadi named Rouzek head of the Taiz Operations Rooms, coordinating the military campaign, and top commander of a new fighting force, the 5th Presidential Protection Battalion. Hadi’s Defense Ministry also gave Rouzek $12 million for a new offensive against the Houthis. The AP obtained copy of a receipt for the $12 million and a Rouzek aide confirmed the figure.

Rouzek denied any connection to militants, telling the AP that “there is no presence of al-Qaida” in Taiz.

Another coalition-backed warlord is on the U.S. list of designated terrorists due to his ties to al-Qaida.

The warlord, a Salafi known as Sheikh Aboul Abbas, has received millions of dollars from the coalition to distribute among anti-Houthi factions, according to his aide, Adel al-Ezzi. Despite being put on the U.S. list in October, the UAE continues to fund him, al-Ezzi told the AP.

The aide denied any links to militants and dismissed his boss’s designation on the U.S. terror list. Nevertheless, he acknowledged that “al-Qaida has fought on all the front lines alongside all factions.”

Right after the AP team spoke to him in Taiz, the team saw al-Ezzi meeting with a known senior al-Qaida figure, warmly hugging him outside the home of another former AQAP commander.

Aboul Abbas runs a coalition-funded militia controlling several districts in Taiz. A 2016 video produced by al-Qaida shows militants in black uniforms with al-Qaida’s logo fighting alongside other militias in districts known to be under his control.

A former security official in Taiz said militants and Aboul Abbas’ forces attacked security headquarters in 2017 and freed a number of al-Qaida suspects. The officer said he reported the attack to the coalition, only to learn soon after that it gave Aboul Abbas 40 more pick-up trucks.

“The more we warn, the more they are rewarded,” the officer said. “Al-Qaida leaders have armored vehicles given to them by the coalition while security commanders don’t have such vehicles.”

Text from the AP news story, AP Investigation: US allies, al-Qaida battle rebels in Yemen, by Maggie Michael, Trish Wilson and Lee Keath.

Wilson contributed from Washington. Keath contributed from Beirut. AP correspondent Desmond Butler also contributed to this report.