OPINION

WYNN, Circuit Judge:

Ivan Teleguz, convicted of capital murder and sentenced to death in Virginia, appeals from the district court's dismissal of his 28 U.S.C. § 2254 petition for habeas corpus relief. We granted a certificate of appealability to determine whether the district court abused its discretion in denying Teleguz's request for an evidentiary hearing to develop his claim of actual innocence, which, under Schlup v. Delo, 513 U.S. 298, 115 S.Ct. 851, 130 L.Ed.2d 808 (1995), would allow the district court to address Teleguz's procedurally defaulted constitutional claims. We hold that the district court abused its discretion in failing to conduct a sound and thorough analysis of Teleguz's Schlup gateway innocence claim as required by our decision in Wolfe v. Johnson, 565 F.3d 140, 163 (4th Cir.2009), and we remand for further proceedings.

I.

On February 9, 2006, a jury convicted Teleguz of capital murder for hire after his former girlfriend, Stephanie Sipe, was found dead in the apartment she shared with Teleguz's infant son. Although DNA evidence linked Michael Hetrick to the murder, Hetrick testified at Teleguz's trial that Teleguz had hired him to commit the crime. Hetrick's allegations were corroborated by two additional witnesses: Edwin Gilkes and Aleksey Safanov. Gilkes testified that he had been present at a birthday party where Teleguz hired Hetrick to commit the murder. Gilkes also testified that he accompanied Hetrick to Sipe's apartment and waited outside for Hetrick during the murder. Gilkes further claimed that he was afraid of Teleguz because he had heard rumors that Teleguz was a member of the Russian mafia, as well as a specific account of a murder committed by Teleguz in Ephrata, Pennsylvania. According to Gilkes, Teleguz had shot a Russian criminal in the street outside the Ephrata Recreation Center.

Safanov testified that Teleguz attempted to hire him to murder Sipe so that Teleguz would no longer be required to pay child support. Safanov also testified that Teleguz had spoken to him after the murder, complaining that "the black man" he had hired to kill Sipe had left blood at the scene, and offering Safanov money if he would "eliminate [the] killer." J.A. 325. Although other evidence was presented at trial, the Supreme Court of Virginia explained that, "in order to return a guilty verdict, the jury had to believe the testimony of Safanov, Gilkes, and Hetrick." Teleguz v. Commonwealth, 273 Va. 458, 643 S.E.2d 708, 728 (2007) ("Teleguz I").

On February 14, 2006, the jury recommended a death sentence after finding that two statutory aggravating factors were present: vileness and future dangerousness. Following Teleguz's appeal, the Supreme Court of Virginia affirmed his conviction and sentence. Teleguz I, 643 S.E.2d at 732. He then filed a petition for writ of habeas corpus in state court, which the Supreme Court of Virginia dismissed. Teleguz v. Warden of Sussex I State Prison, 279 Va. 1, 688 S.E.2d 865, 879 (2010). On November 12, 2010, Teleguz filed a petition for writ of habeas corpus in the United States District Court for the Western District of Virginia, asserting various grounds for relief. Some of Teleguz's claims had been adjudicated on the merits by the Supreme Court of Virginia, while others had been procedurally defaulted. Teleguz argued that, pursuant to the Supreme Court's decision in Schlup, 513 U.S. 298, 115 S.Ct. 851, the district court should consider the merits of his procedurally defaulted claims because new and reliable evidence established that he was actually innocent of Sipe's murder ("Schlup gateway innocence claim").

In support of his Schlup gateway innocence claim, Teleguz offered several categories of evidence. First, he presented affidavits of third-party witnesses who claimed that Teleguz did not attend the birthday party during which he was alleged to have hired Hetrick to kill Sipe. Second, he offered police reports and affidavits to establish that no murder occurred outside the Ephrata Recreation Center, that no murder that occurred in Ephrata prior to Teleguz's trial remains unsolved, and that the only murder involving a Russian victim occurred at a private residence. Third, Teleguz presented affidavits in which Gilkes and Safanov recanted the testimony they offered at Teleguz's trial. Gilkes now claims that he was coerced into testifying against Teleguz by the prosecutor, who "made clear that if [he] did not, [he] would have been the one on death row today, not Teleguz." J.A. 1281. Gilkes executed affidavits in both 2008 and 2010 denying that Teleguz hired Hetrick to kill Sipe. Safanov currently resides in Kazakhstan, but was contacted by lawyers from Teleguz's defense team. According to their affidavits, Safanov now insists that he never discussed Sipe's murder with Teleguz and agreed to testify during Teleguz's trial only because he believed that if he cooperated with the prosecutor, he would be eligible for a visa allowing him to stay in the United States despite pending federal gun charges.

On August 1, 2011, the district court issued an opinion and order denying Teleguz habeas relief. Teleguz v. Kelly, 824 F.Supp.2d 672, 723 (W.D.Va.2011) ("Teleguz II"). We granted a certificate of appealability to determine whether the district court abused its discretion in denying Teleguz's request for an evidentiary hearing pursuant to Schlup v. Delo, 513 U.S. 298, 115 S.Ct. 851.1

II.

We review a district court's denial of habeas relief de novo and its decision not to grant an evidentiary hearing for abuse of discretion. Wolfe, 565 F.3d at 160. When a court bases its decision on an error of law, it necessarily abuses its discretion. Id.

A.

"In disposing of a § 2254 habeas corpus petition" federal courts are "substantially constrain[ed]" in their review of state court convictions by the Antiterrorism and Effective Death Penalty Act of 1996 ("AEDPA"). Id. at 159. The AEDPA was "designed to further the principles of comity, finality, and federalism" by limiting federal habeas proceedings. Sharpe v. Bell, 593 F.3d 372, 379 (4th Cir.2010) (quotation marks omitted). Accordingly, if a state court adjudicates a petitioner's claims on the merits, a federal court may only award habeas relief if the resulting state court decision "[i]s contrary to or involved an unreasonable application of federal law" or "[i]s based on an unreasonable determination of the facts in light of the evidence" that was before it. 28 U.S.C. § 2254(d). "A state court's decision is `contrary to' clearly established federal law only if it is `substantially different' from the relevant Supreme Court precedent; it is `an unreasonable application of' clearly established federal law only if it is `objectively unreasonable.'" Wolfe, 565 F.3d at 159 (quoting Williams v. Taylor, 529 U.S. 362, 405, 409, 120 S.Ct. 1495, 146 L.Ed.2d 389 (2000)).

Further, a federal court ordinarily may not consider claims that a petitioner failed to raise at the time and in the manner required under state law unless "the prisoner demonstrates cause for the default and prejudice from the asserted error." House v. Bell, 547 U.S. 518, 536, 126 S.Ct. 2064, 165 L.Ed.2d 1 (2006). However, in Schlup, 513 U.S. 298, 115 S.Ct. 851, the Supreme Court recognized that in certain exceptional cases, a compelling showing of actual innocence would enable a federal court to consider the merits of a petitioner's otherwise defaulted claims. In these cases, new evidence "establish[es] sufficient doubt about [a petitioner's] guilt to justify the conclusion that his execution would be a miscarriage of justice unless his conviction was the product of a fair trial." Id. at 316, 115 S.Ct. 851 (emphasis in original).

Courts have consistently emphasized that actual innocence for the purposes of Schlup is a procedural mechanism rather than a substantive claim. See, e.g., Sibley v. Culliver, 377 F.3d 1196, 1207 n. 9 (11th Cir.2004) (distinguishing between a "substantive claim for relief upon which the petition for habeas corpus is based" and a Schlup "gateway through which a habeas petitioner must pass" to have his substantive claims heard on the merits).2 In other words, although a petitioner claims actual innocence for the purposes of asserting a Schlup claim, this innocence claim "does not by itself provide a basis for relief. Instead, his claim for relief relies critically on the validity" of his procedurally defaulted claims. Coleman v. Hardy, 628 F.3d 314, 318 (7th Cir.2010) (quotation marks omitted).

When a petitioner raises a Schlup gateway actual innocence claim, it must be supported by "new reliable evidence." Schlup, 513 U.S. at 324, 115 S.Ct. 851. However, in its consideration of a petitioner's Schlup gateway actual innocence claim, the district court "must consider `all the evidence' old and new, incriminating and exculpatory, without regard to whether it would necessarily be admitted under `rules of admissibility that would govern at trial.'" House, 547 U.S. at 537, 126 S.Ct. 2064 (quoting Schlup, 513 U.S. at 327-28, 115 S.Ct. 851) (emphasis added) (quotation marks omitted). In light of this evidence, the district court must determine whether "it is more likely than not that no reasonable juror would have found [the] petitioner guilty beyond a reasonable doubt." Schlup, 513 U.S. at 327, 115 S.Ct. 851. If the district court finds that, "more likely than not any reasonable juror would have reasonable doubt" as to the petitioner's guilt, then the petitioner has satisfied the Schlup standard, and the district court must review the petitioner's procedurally defaulted claims. House, 547 U.S. at 538, 126 S.Ct. 2064.

B.

Here, Teleguz's habeas petition asserted a Schlup gateway innocence claim to allow the district court to consider the merits of his procedurally defaulted claims. Teleguz argues that he met the Schlup standard with an extraordinary showing of actual innocence because "two of the prosecution's three critical witnesses hav[e] admitted that their trial testimony was false, [and] it is [therefore] ... more likely than not that any reasonable juror presented with all the evidence, old and new, incriminating and exculpatory, would have a reasonable doubt about Teleguz's guilt." Appellant's Br. 29 (quotation marks omitted). Although we appreciate that the district court "attentively managed complex proceedings" and "carefully reviewed the extensive record" that was before it in this case, House, 547 U.S. at 540, 126 S.Ct. 2064, we are unable to conclude, based on the district court's opinion, that Teleguz's Schlup gateway innocence claim was properly analyzed and resolved by the district court.

The district court correctly set out the Schlup standard in its explanation of the relevant law.3 However, as we explained in Wolfe, "a sound analysis of the Schlup issue is essential to properly resolve these § 2254 proceedings." 565 F.3d at 163 (emphasis added). Notwithstanding this requirement, in addressing Teleguz's procedurally defaulted claims, the district court simply stated that "Teleguz has not shown cause and prejudice or a fundamental miscarriage of justice to excuse the default." Teleguz II, 824 F.Supp.2d at 698; see also id. at 695 ("Teleguz has failed to show cause for the default and... has not shown a fundamental miscarriage of justice that would excuse the default."); id. at 708, 709 ("Teleguz has failed to show cause and prejudice or a miscarriage of justice."); id. at 696 ("[T]here is no fundamental miscarriage of justice to excuse that default."). Nowhere in its order does the district court more thoroughly or directly consider Teleguz's Schlup gateway innocence claim.4 Consequently, this Court is left with the district court's conclusory explanations, which do not provide sufficient analysis to enable us to review the reasons for, or scope of, the district court's denial of Teleguz's Schlup gateway innocence claim.

Further, that the district court addressed the cause and prejudice standard and the miscarriage of justice standard in the same sentences indicates that the district court likely based its analysis on a mistake of law, by applying its Schlup analysis to individual procedurally defaulted claims. See, e.g., Teleguz II, 824 F.Supp.2d at 698 ("Teleguz has not shown cause and prejudice or a fundamental miscarriage of justice to excuse the default."). While both the cause and prejudice standard and Schlup's fundamental miscarriage of justice standard excuse a procedural default and allow a federal court to review defaulted claims on the merits, a petitioner must meet the cause and prejudice standard with respect to each claim. McCleese v. United States, 75 F.3d 1174, 1179 (7th Cir.1996) ("Claims are reviewed individually for purposes of determining whether they overcome a procedural default; each claim must meet the cause and prejudice test.").

By contrast, a petitioner's satisfaction of the Schlup standard does not require a showing that a fundamental miscarriage of justice caused or underlies each procedurally defaulted claim. Rather, to satisfy the Schlup standard, a petitioner must instead demonstrate that the totality of the evidence would prevent any reasonable juror from finding him guilty beyond a reasonable doubt, such that his incarceration is a miscarriage of justice. See Schlup, 513 U.S. at 327, 115 S.Ct. 851. If a petitioner passes through the Schlup gateway by satisfying this standard, the district court then considers, and reaches the merits of, all of the petitioner's procedurally defaulted claims.

Other portions of the district court's opinion also support our determination that the district court erroneously applied its Schlup analysis individually to each procedurally defaulted claim rather than to the totality of the evidence. See, e.g., Teleguz II, 824 F.Supp.2d at 711-12 (examining a procedurally defaulted claim on the merits and concluding, "I do not find this issue significant enough to excuse Teleguz's procedural default"). The Commonwealth similarly mischaracterizes the Schlup inquiry in its brief, arguing that the court need not engage in Schlup analysis because Teleguz "never identified or discussed how any particular defaulted claim would qualify under the gateway standard[ ] of Schlup," and claiming instead that Teleguz "simply contended that he was innocent, that he had defaulted claims, and that he therefore was entitled to relief." Appellee's Br. 25. We reject the Commonwealth's contention that "federal habeas courts may not entertain any argument of [a Schlup gateway] innocence [claim] that is not causally connected to a defaulted claim of constitutional error." Appellee's Br. 21. We find no jurisprudential support for a requirement that a causal relationship exist between a petitioner's evidence of actual innocence and a petitioner's procedurally defaulted claims. In House, for example, a petitioner convicted of capital murder claimed that DNA evidence proved he had not committed the crime, and that his counsel's ineffectiveness had resulted in his conviction. 547 U.S. at 533, 540, 126 S.Ct. 2064. The Supreme Court examined the DNA evidence and witness testimony that House offered in support of his actual innocence of the crime, and held that he had met the Schlup gateway innocence standard without any discussion of his counsel's performance at trial. See id. at 555, 126 S.Ct. 2064 ("House has satisfied the gateway standard set forth in Schlup and may proceed on remand with procedurally defaulted constitutional claims.").5

Thus, a district court's inquiry into a Schlup gateway innocence claim requires an examination of all of the evidence and a threshold determination about the petitioner's claim of innocence that is separate from its inquiry into the fairness of his trial. See Schlup, 513 U.S. at 327, 115 S.Ct. 851 (noting that the "standard is intended to focus the inquiry on actual innocence"). The district court must make a holistic determination of how a reasonable juror would perceive all of the evidence in the record. Only if the district court determines that a reasonable juror would more than likely have a reasonable doubt does it then consider the petitioner's procedurally defaulted claims. Because we are unable to conclude that the district court engaged in the rigorous Schlup analysis required by Wolfe, we vacate and remand on this issue.

III.

Because we remand for further analysis of Teleguz's Schlup gateway innocence claim, the district court will again be faced with the issue of whether to conduct an evidentiary hearing to allow Teleguz to develop this innocence claim. We therefore turn next to this issue.

In its detailed opinion, the district court did not explain its decision not to conduct an evidentiary hearing on Teleguz's Schlup gateway innocence claim. On remand, the district court should address whether Teleguz should be granted an evidentiary hearing.6 The district court should consider the particular facts raised by the petitioner in support of his actual innocence claim in determining whether an evidentiary hearing is warranted. Compare Cristin v. Brennan, 281 F.3d 404, 417 (3d Cir.2002) (affirming the district court's decision to hold an evidentiary hearing to determine if petitioner met the threshold of actual innocence), with Thomas v. Taylor, 170 F.3d 466, 475 (4th Cir.1999) (affirming the district court's denial of evidentiary hearing on actual innocence when petitioner's requested discovery could not establish his actual innocence).

This Court has counseled that, when a witness providing the "only direct evidence implicating [a petitioner] in the murder-for-hire scheme" recants his testimony, this recantation "strongly suggests that an evidentiary hearing may be warranted." Wolfe, 565 F.3d at 170. We explained that an evidentiary hearing may be necessary to assess whether recantations are credible, or whether "`the circumstances surrounding the recantation[s] suggest [that they are] the result of coercion, bribery or misdealing.'" Id. at 169 (quoting United States v. Johnson, 487 F.2d 1278, 1279 (4th Cir.1973)). This type of credibility determination, required for Schlup analysis, may be more difficult on a cold record. Cf. Coleman, 628 F.3d at 320-21 (remanding for an evidentiary hearing to "evaluate the reliability" of the recantation of a codefendant whose "reputation for honesty is weak"). The district court should also consider the "heightened need for fairness in the administration of death[,] ... born of the appreciation that death truly is different from all other punishments a society inflicts upon its citizens." Callins v. Collins, 510 U.S. 1141, 1149, 114 S.Ct. 1127, 127 L.Ed.2d 435 (1994) (Blackmun, J., dissenting from denial of certiorari).

The Commonwealth correctly notes in its brief that a district court's ability to make factual determinations is constrained by 28 U.S.C. § 2254(e)(1), which provides that any "determination of a factual issue made by a State court shall be presumed to be correct." Thus, when a state court has made a factual determination bearing on the resolution of a Schlup issue, the petitioner bears the burden of rebutting this presumption by "clear and convincing evidence." Sharpe, 593 F.3d at 378.

Here, however, the Supreme Court of Virginia has not assessed the credibility of Teleguz's recantations. It is well established that the district court is permitted under Schlup to "make some credibility assessments" when, as here, a state court has not evaluated the reliability of a petitioner's "newly presented evidence [that] may indeed call into question the credibility of the witnesses presented at trial." Schlup, 513 U.S. at 330, 115 S.Ct. 851. Accordingly, the district court may make determinations about "the probative force of relevant evidence that was either excluded or unavailable at trial," id. at 327-28, 115 S.Ct. 851, and "assess how reasonable jurors would react to the overall, newly supplemented record," House, 547 U.S. at 538, 126 S.Ct. 2064, but the district court may not reject the factual findings of a state court absent clear error. Sharpe, 593 F.3d at 379.

IV.

For the foregoing reasons, we vacate the district court's decision in part and remand for further proceedings.

VACATED IN PART AND REMANDED