KAVANAUGH, Circuit Judge:

In response to al Qaeda's attacks against the United States on September 11, 2001, Congress passed and President Bush signed the Authorization for Use of Military Force. The AUMF provides:

That the President is authorized to use all necessary and appropriate force against those nations, organizations, or persons he determines planned, authorized, committed, or aided the terrorist attacks that occurred on September 11, 2001, or harbored such organizations or persons, in order to prevent any future acts of international terrorism against the United States by such nations, organizations or persons.

Pub.L. No. 107-40, § 2(a), 115 Stat. 224 (2001); see U.S. CONST. art. I. § 8. The AUMF, among other things, authorizes the Executive Branch to detain for the duration of hostilities those individuals who are part of al Qaeda or the Taliban. See Hamdi v. Rumsfeld, 542 U.S. 507, 518, 124 S.Ct. 2633, 159 L.Ed.2d 578 (2004).

Under the AUMF, the U.S. military currently holds Uthman Abdul Rahim Mohammed Uthman at the U.S. naval base in Guantanamo Bay, Cuba. Exercising his right under the U.S. Constitution to judicial review of the basis for his detention, Uthman filed a petition for a writ of habeas corpus in the U.S. District Court for the District of Columbia. See Boumediene v. Bush, 553 U.S. 723, 128 S.Ct. 2229, 171 L.Ed.2d 41 (2008). Uthman contended that he was not part of al Qaeda and therefore was not properly detained. Applying a "command structure test," the District Court ruled that the Government had not proved that Uthman was part of al Qaeda. The District Court therefore granted the petition and ordered Uthman released from U.S. custody.

In decisions issued since the District Court's judgment in this case, this Court has rejected "command structure" as the test for determining whether someone is part of al Qaeda. Our cases have held that the "determination of whether an individual is `part of al-Qaida `must be made on a case-by-case basis by using a functional rather than a formal approach and by focusing upon the actions of the individual in relation to the organization.'" Salahi v. Obama, 625 F.3d 745, 751-52 (D.C. Cir. 2010) (quoting Bensayah v. Obama, 610 F.3d 718, 725 (D.C. Cir. 2010)).

Applying the functional standard mandated by our precedents, we conclude that the facts found by the District Court, along with uncontested facts in the record, demonstrate that Uthman more likely than not was part of al Qaeda. We therefore reverse the judgment of the District Court and remand with instructions to deny the petition for a writ of habeas corpus.

I

Uthman Abdul Rahim Mohammed Uthman, a Yemeni man, was captured at the Afghan-Pakistani border near Tora Bora on December 15, 2001. He was captured in a small group that included two al Qaeda members who were Osama bin Laden bodyguards and another man who was a Taliban fighter. Tora Bora is a cave complex in the mountains of eastern Afghanistan. Al Qaeda forces gathered there in December 2001 to wage a major battle against the United States and its allies.

Soon after his capture, Uthman was transferred to the U.S. naval base in Guantanamo Bay, Cuba. He has been detained at Guantanamo since January 2002.

In 2004, Uthman filed a petition for a writ of habeas corpus in the U.S. District Court for the District of Columbia challenging the basis for his detention. The Government asserted that Uthman was part of al Qaeda and therefore may be detained for the duration of the war against al Qaeda pursuant to the Authorization for Use of Military Force. See Hamdi v. Rumsfeld, 542 U.S. 507, 518, 124 S.Ct. 2633, 159 L.Ed.2d 578 (2004); Bensayah v. Obama, 610 F.3d 718, 724-25 (D.C. Cir. 2010).

The District Court stated that "the key question" in determining someone's membership in al Qaeda "is whether an individual receives and executes orders from the enemy force's combat apparatus." Abdah v. Obama, 708 F.Supp.2d 9, 13 (D.D.C. 2010) (internal quotation marks and alterations omitted). The District Court derived that test from two previous district court opinions applying this "command structure test." See id. at 12-13 (citing Hamlily v. Obama, 616 F.Supp.2d 63 (D.D.C. 2009), and Gherebi v. Obama, 609 F.Supp.2d 43 (D.D.C. 2009)). After examining the evidence, the District Court concluded that the Government did "not convince the Court by a preponderance of the evidence that Uthman received and executed orders from Al Qaeda." Id. at 22. On that basis, the District Court granted Uthman's petition for a writ of habeas corpus. Id. at 23.

Several of this Court's cases — all decided after the District Court granted Uthman's petition — have held that the "command structure test" does not reflect the full scope of the Executive's detention authority under the AUMF. "These decisions make clear that the determination of whether an individual is `part of al-Qaida `must be made on a case-by-case basis by using a functional rather than a formal approach and by focusing upon the actions of the individual in relation to the organization.`" Salahi v. Obama, 625 F.3d 745, 751-52 (D.C. Cir. 2010) (quoting Bensayah, 610 F.3d at 725); see also Awad v. Obama, 608 F.3d 1, 11 (D.C. Cir. 2010) ("Nowhere in the AUMF is there a mention of command structure."). To be sure, demonstrating that someone is part of al Qaeda's command structure is sufficient to show that person is part of al Qaeda. But it is not necessary. See, e.g., Awad, 608 F.3d at 11. Indicia other than the receipt and execution of al Qaeda's orders may prove "that a particular individual is sufficiently involved with the organization to be deemed part of it." Bensayah, 610 F.3d at 725 (citing Awad, 608 F.3d at 11). It is thus possible that someone may "properly be considered `part of al-Qaida even if he never formally received or executed any orders." Salahi, 625 F.3d at 752 (citing Awad, 608 F.3d at 3-4, 11).

In this case, the question therefore is whether, under the functional test mandated by our precedents, the established facts — that is, those facts found by the District Court or otherwise uncontested — show that Uthman more likely than not was part of al Qaeda. Our analysis of that question is de novo. See Barhoumi v. Obama, 609 F.3d 416, 423 (D.C. Cir. 2010).

II

In analyzing whether Uthman more likely than not was part of al Qaeda, we consider the following facts, which were found by the District Court or are otherwise uncontested:

• Uthman was captured in December 2001 in the vicinity of Tora Bora, an isolated, mountainous area where al Qaeda forces had gathered to fight the United States and its allies.

• When captured, Uthman was traveling with a small group of men, two of whom were al Qaeda members and bodyguards for Osama bin Laden and one of whom was a Taliban fighter.

• Leading up to his capture, Uthman's journey began at a religious school in Yemen where al Qaeda had successfully recruited fighters. The two al Qaeda members and Osama bin Laden bodyguards who were later captured with Uthman, as well as the Taliban fighter captured with Uthman, also attended the Furqan Institute.

• Uthman traveled to Afghanistan along a route used by al Qaeda recruits.

• Uthman lied to hide the fact that someone else paid for his travel to Afghanistan.

• While in Afghanistan, Uthman was seen at an al Qaeda guesthouse.

• Uthman's explanation of why he went to Afghanistan and why he was traveling in a small group that included al Qaeda members and a Taliban fighter near Tora Bora during the battle there involves a host of unlikely coincidences.

Uthman argues that those facts do not add up to his being part of al Qaeda. As we will explain, we conclude that those facts, taken together, are more than sufficient to show that Uthman more likely than not Tas part of al Qaeda. First, Uthman was captured on December 15, 2001, "in the vicinity of Tora Bora." Abdah v. Obama, 708 F.Supp.2d 9, 22 (D.D.C. 2010). As the District Court noted, it was "widely known" that Tora Bora was a battleground between al Qaeda and the United States and "few, if any noncombatants would have been in the vicinity during this time." Id. at 19 n. 11. Because "few, if any" non-combatants were near Tora Bora, it follows that most, if not all, of those in the vicinity of Tora Bora on December 15, 2001, were combatants. In a prior case, we found it significant that a detainee was captured near Tora Bora in late 2001. See Al Odah v. United States, 611 F.3d 8, 11, 16 (D.C. Cir. 2010). In short, the fact that Uthman was captured in December 2001 near Tora Bora suggests that he was affiliated with al Qaeda.

Second, the company Uthman was keeping when he was captured near Tora Bora in December 2001 makes it even more likely that he was part of al Qaeda. See Abdah, 708 F.Supp.2d at 22 (Uthman "was with Al Qaeda members in the vicinity of Tora Bora"). Uthman admits that, when captured, he was part of a small group including at least five other Yemeni men. Two of those men were al Qaeda members and have since confessed to being bodyguards for Osama bin Laden. Another fought with the Taliban against United States forces. One of the bin Laden body-guards in Uthman's band described the group as "brothers" retreating from battle. In our prior cases, we have stated that evidence of association with other al Qaeda members is itself probative of al Qaeda membership. Cf. Al-Adahi v. Obama, 613 F.3d 1102, 1107 (D.C. Cir. 2010); Awad v. Obama, 608 F.3d 1, 9-10 (D.C. Cir. 2010); id. at 3 (noting that al Qaeda fighters treated Awad "as one of their own"); see also Salahi v. Obama, 625 F.3d 745, 753 (D.C. Cir. 2010) (district court may be able to "infer from Salahi's numerous ties to known al-Qaida operatives that he remained a trusted member of the organization"). So it is here.

Being captured in the company of a Taliban fighter and two al Qaeda members and Osama bin Laden bodyguards 12 miles from Tora Bora in December 2001 might not be precisely the same as being captured in a German uniform 12 miles from the Normandy beaches in June 1944. But it is still, at a minimum, highly significant. And absent a credible alternative explanation, the location and date of Uthman's capture, together with the company he was keeping, strongly suggest that he was part of al Qaeda. And there is more.

Third, the narrative of Uthman's journey before his capture suggests that it was not an accident that he ended up near Tora Bora on December 15, 2001, in the company of two al Qaeda members who were Osama bin Laden's bodyguards, as well as a Taliban fighter. That narrative begins with Uthman's studies at the Furqan Institute, a religious school "at which other men were recruited to fight for Al Qaeda." Abdah, 708 F.Supp.2d at 22. Uthman downplays this particular fact, noting that most students at the school probably did not become al Qaeda fighters. Uthman's argument ignores two points. First, attendance at such a school — which was a fruitful al Qaeda recruiting ground — is a fact that, while perhaps not alone of great significance, can assume greater significance when considered in light of other facts suggesting al Qaeda membership. Cf. Al-Adahi, 613 F.3d at 1105-09; Al Odah, 611 F.3d at 16. Second, the two al Qaeda members and Osama bin Laden bodyguards and the Taliban fighter captured with Uthman in the vicinity of Tora Bora also attended the Furqan Institute. Uthman admitted he knew all of them from the Institute, including the Osama bin Laden bodyguard and former Furqan Institute student who described the group as "brothers." Uthman's long association with those three fellow travelers, dating back to their shared time at an al Qaeda recruiting ground, renders it rather unlikely that their travel together near al Qaeda's embattled stronghold at Tora Bora in December 2001 was a coincidental reunion of old schoolmates. Cf. Salahi 625 F.3d at 753; Al-Adahi 613 F.3d at 1105, 1107; Awad, 608 F.3d at 3, 9-10.

Fourth, after studying at the Furqan Institute, Uthman "traveled to Afghanistan along a route also taken by Al Qaeda recruits." Abdah, 708 F.Supp.2d at 22. Specifically, Uthman flew from Sana'a, Yemen, to Karachi, Pakistan. From Karachi, he traveled by bus to Quetta, Pakistan, and then by taxi to a Taliban office there. From Quetta, a Taliban official arranged for Uthman's transportation to Kandahar, Afghanistan. Uthman's route is similar to the paths of admitted al Qaeda members now in U.S. custody. This Court has stated that traveling to Afghanistan along a distinctive path used by al Qaeda members can be probative evidence that the traveler was part of al Qaeda. See Al Odah, 611 F.3d at 16. Uthman again argues that this fact alone is not significant, as people who were not al Qaeda recruits may have followed the same track. But the fact that Uthman followed a common al Qaeda route nonetheless makes it somewhat more likely that he was an al Qaeda recruit. See Al-Adah 613 F.3d at 1105; cf. Bourjaily v. United States, 483 U.S. 171, 179-80, 107 S.Ct. 2775, 97 L.Ed.2d 144 (1987) ("individual pieces of evidence, insufficient in themselves to prove a point, may in cumulation prove it").

Fifth, Uthman's route to Afghanistan is even more suspicious because he lied about how he paid for the trip. The Government contends that a Yemeni sheikh who supported terrorism funded Uthman's journey. In his sworn statement to the District Court, Uthman said he raised the funds himself primarily by working at summer jobs selling food at a roadside shack. The Government says this explanation is preposterous, observing that Uthman would have had to earn more than three times the average Yemeni's annual income in only a few summers' unskilled work. The District Court agreed with the Government, finding that Uthman received the funds from the sheikh, as Uthman originally told interrogators. Abdah, 708 F.Supp.2d at 22. Although the District Court made no finding as to whether that sheikh supported terrorism, its determination that Uthman's trip to Afghanistan was financed by the sheikh necessarily means the court found Uthman's sworn statement that he paid for his own travel to be false. Uthman's false explanation is relevant here because, as we have said in another case, "false exculpatory statements are evidence — often strong evidence — of guilt." Al-Adahi, 613 F.3d at 1107 (citing United States v. Penn, 974 F.2d 1026, 1029 (8th Cir. 1992), and United States v. Meyer, 733 F.2d 362, 363 (5th Cir. 1984)).

Sixth, once he reached Afghanistan, Uthman was seen at an al Qaeda guest-house. See Abdah, 708 F.Supp.2d. at 22. In two prior cases, this Court has stated that staying at an al Qaeda guesthouse is "powerful — indeed `overwhelming' — evidence" that an individual is part of al Qaeda. Al-Adahi, 613 F.3d at 1108 (quoting Al-Bihani v. Obama, 590 F.3d 866, 873 n. 2 (D.C. Cir. 2010)) (alterations omitted). The reason for that assessment is plain: It is highly unlikely that a visitor to Afghanistan would end up at an al Qaeda guest-house by mistake, either by the guest or by the host. Uthman retorts that he was only seen at an al Qaeda guesthouse, which does not necessarily mean that he was staying there. True, but just being present at an al Qaeda guesthouse is hardly the kind of innocent fact that can be tossed aside as insignificant. Moreover, absent another explanation (and Uthman provides none), the most plausible reason for Uthman's presence at an al Qaeda guesthouse is that he was affiliated with al Qaeda and staying at the guesthouse. See Al-Adahi, 613 F.3d at 1108. That implication is strongly buttressed by the fact that Uthman did not have his passport when he was captured. As this Court has explained, surrendering one's passport was "standard al Qaeda and Taliban operating procedure[]" when checking into an al Qaeda guesthouse in Afghanistan. Al Odah, 611 F.3d at 15.

Seventh, Uthman's account of his activity in Afghanistan and Pakistan involves many coincidences that are perhaps possible, but not likely. According to Uthman, he went to Afghanistan to teach the Koran. As of September 11, 2001, he was in Kabul, teaching the Koran, although he does not remember the names of any of his students and cannot describe his school in Kabul. Unlike many civilians living in Kabul at the time, Uthman remained in the capital as the United States began its attack against the Taliban regime. Only after the Taliban and its al Qaeda allies lost control of Kabul did Uthman choose to leave. Although he wished to flee to Pakistan, Uthman did not take the eastward road through the Khyber Pass that leads directly to Pakistan. Instead, Uthman took the long way home. He fled south, parallel to Pakistan's border, into rugged, mountainous terrain — following his interpreter, he claims. Unfortunately, as the story goes, his path led him near Tora Bora, where Osama bin Laden and Ayman al-Zawahiri happened to have relocated and where it was widely known that al Qaeda was gathering for a major battle against the United States and its allies. There, in the Afghan mountains, he chanced to meet up with schoolmates from his school days in Yemen. Unfortunately for Uthman, those schoolmates also happened to be two al Qaeda members who were Osama bin Laden bodyguards and a Taliban fighter. Then, Uthman finally chose to enter Pakistan — as it turns out, at the height of the U.S. bombardment of Tora Bora and al Qaeda's flight from Afghanistan — where he says he was mistaken for an al Qaeda fighter and detained.

Uthman's account piles coincidence upon coincidence upon coincidence. Here, as with the liable or guilty party in any civil or criminal case, it remains possible that Uthman was innocently going about his business and just happened to show up in a variety of extraordinary places — a kind of Forrest Gump in the war against al Qaeda. But Uthman's account at best strains credulity; and the far more likely explanation for the plethora of damning circumstantial evidence is that he was part of al Qaeda. When presented with similar circumstantial evidence in prior cases, we have had no trouble reaching the conclusion that the detainee more likely than not was part of al Qaeda. See Al-Adahi, 613 F.3d 1102; Al Odah, 611 F.3d 8; Barhoumi v. Obama, 609 F.3d 416 (D.C. Cir. 2010); Awad, 608 F.3d 1; AV-Bihani, 590 F.3d 866. So too here.

* * *

To sum up, in the years leading up to his capture, Uthman's life was intertwined with al Qaeda's operations. Uthman attended a school in Yemen where al Qaeda successfully recruited. He traveled to Afghanistan along a route used by al Qaeda recruits. He lied about how he paid for that journey. He was seen at an al Qaeda guesthouse in Afghanistan. He traveled to an isolated mountainous region near what was then al Qaeda's last stronghold in Afghanistan, during a major battle there. He was captured on December 15, 2001, in a small group that included two al Qaeda members who were Osama bin Laden's bodyguards and a Taliban fighter. He did not have a passport with him. And he has not credibly explained why he went to Afghanistan or how he found himself traveling with a small group that included two al Qaeda members who were Osama bin Laden bodyguards and a Taliban fighter near Tora Bora in December 2001.

We do "not weigh each piece of evidence in isolation, but consider all of the evidence taken as a whole." Al Odah, 611 F.3d at 15 (quoting Awad, 608 F.3d at 6-7); see also Al-Adahi 613 F.3d at 1105-07. Uthman's actions and recurrent entanglement with al Qaeda show that he more likely than not was part of al Qaeda. We therefore reverse the judgment of the District Court and remand with instructions to deny Uthman's petition for a writ of habeas corpus.

So ordered.