Shawn Marcus Henry seeks a certificate of appealability (COA) as mandated by 28 U.S.C. § 2253(c) to appeal the district court’s denial of his 28 U.S.C. § 2254 petition. Henry’s petition requires us to determine the proper standard for granting a COA when, as was the case here, the district court disposes of a petition on procedural grounds.
I. Procedural History
Henry was accused of entering the apartment of an acquaintance and shooting him. A Florida state court convicted Henry of first-degree murder and armed burglary, crimes for which he is currently serving concurrent sentences. Following affirmance on direct appeal, Henry filed a petition for postconviction relief under Fla. R. Crim. P. 3.850. In his 3.850 petition, Henry asserted two claims for relief: (1) that his trial counsel had been ineffective for failing to call a particular witness, Edwin Heyliger; and (2) that his trial counsel had been ineffective for advising Henry, on the basis of erroneous information regarding his prior criminal background and because of a conflict of interest, not to take the stand on his own behalf. The trial judge denied relief on both of Henry’s claims without conducting an evidentiary hearing.
Henry then appealed the denial of his 3.850 petition. In his briefs, Henry characterized the issue on appeal solely as whether “[t]he trial court erred in denying defendant’s motion for postconviction relief without an evidentiary hearing.” (R.-5, Ex. E at 7, Ex. G at 3.) In arguing the issue, however, the briefs both presented facts and cited law relevant to the substance of his ineffective-assistance claims. The appeals court affirmed without opinion.
Henry then filed the instant federal ha-beas corpus petition. Again, he raised the same two ineffective-assistance claims. The district judge referred the matter to a magistrate judge for a report and recommendation. The magistrate judge recommended that the petition be dismissed because Henry had failed to exhaust his claims in state court. Specifically, he noted that the substance of Henry’s ineffective-assistance claims had only been brought forth “tangentially from the issue specified in the appeal” — i.e., tangentially from the question whether the trial court should have granted an evidentiary hearing. (R.-7 at 4.) As an alternative basis for decision, the report and recommendation also addressed the merits of Henry’s ineffective-assistance claims and found them lacking. Following receipt and consideration of Henry’s objections to the magistrate judge’s report, the district judge denied Henry’s petition solely because of his failure to exhaust his remedies in state court. The district judge declined to reach the merits of Henry’s ineffective-assistance claims.
Finally, the district judge denied Henry’s request for a COA, and Henry accordingly sought a COA from this court. A motions judge of this court, see Fed. R. App. P. 27(c); 11th Cir. R. 27-l(d)(2), granted a COA as to the exhaustion issue and ordered briefing on the appropriate standard for granting a COA where a district court denies or dismisses a petition for procedural reasons without reaching the merits of the underlying claims. In accordance with Fed. R. App. P. 27(c) and *136411th Cir. R. 27-l(d), we now review the prior decisions regarding the COA in light of the briefs submitted and oral argument. We conclude that the COA was properly granted. We then proceed, using the full presentation of the exhaustion issue provided by the briefs and oral argument, to address the appeal itself.
II. The COA
Henry’s application for a COA raises two questions: (1) whether it is ever appropriate to allow appeals from procedural-rule dismissals of § 2254 petitions; and (2) if it is ever appropriate, when COAs should be granted to permit such appeals. We begin our analysis of both questions with some history. The Antiterrorism and Effective Death Penalty Act of 1996 § 102, 28 U.S.C. § 2253 (Supp. II 1997) (AED-PA), both renamed the certificate needed to appeal the denial or dismissal of a § 2254 petition and changed the standard for issuing that certificate. Prior to AED-PA, petitioners wanting to appeal had to seek a certificate of probable cause (CPC), which required making a “substantial showing of the denial of [a] federal right.” Barefoot v. Estelle, 463 U.S. 880, 893, 103 S.Ct. 3383, 3394, 77 L.Ed.2d 1090 (1983) (alteration in original) (emphasis added) (quoting Steivart v. Beto, 454 F.2d 268, 270 n. 2 (5th Cir.1971)). By contrast, under § 2253(c)(1) federal courts may grant COAs “only if the applicant has made a substantial showing of the denial of a constitutional right.” 28 U.S.C. § 2253(c)(2) (emphasis added).
Despite the change in the statutory language, this circuit has concluded that the pre- and post-AEDPA standards for permitting appeal are identical as they relate to the merit demanded of the constitutional issues raised. See Hardwick v. Sin-gletary, 126 F.3d 1312, 1313 (11th Cir. 1997) (“Notwithstanding a marginal variance in the language identifying the necessary showing with respect to certificates of probable cause and appealability, ... the standard governing certificates of probable cause and certificates of appealability is materially identical.”). Stated fully, that standard requires an appealing petitioner to “ ‘demonstrate that the issues are debatable among jurists of reason; that a court could resolve the issues [in a different manner]; or that the questions are “adequate to deserve encouragement to proceed further.” ’ ” Barefoot, 463 U.S. at 893 n. 4, 103 S.Ct. at 3394 n. 4 (alteration in original) (quoting Gordon v. Willis, 516 F.Supp. 911, 913 (N.D.Ga.1980) (quoting United States ex rel. Jones v. Richmond, 245 F.2d 234 (2d Cir.1957))).
We think that the answers to both of the questions raised by Henry’s petition lie in determining whether the Barefoot standard should be continued not only, as Hardwick holds, with respect to the merit of constitutional claims presented, but also with respect to the district court’s handling of procedural issues raised by a petition. Concluding that the Barefoot standard should be so continued, we hold, first, that appeals from procedural-rule dismissals are appropriate and, second, that the language of Barefoot provides the analytical framework for determining when COAs should be granted to permit such appeals.
The State’s contrary contention notwithstanding, our holding is, in light of historical application of the statute, consistent with the statutory text. It is true that § 2253(c)(2) does not, on its face, provide for COAs to be issued where the district court has denied or dismissed the petition on a noneonstitutional ground. Frequently applied procedural doctrines, such as exhaustion, might seem precluded from review by the shift from “federal right” to “constitutional right.”1 On this view, Hardwick’s observation that the pre- and post-AEDPA appealability standards are *1365“materially identical” is not accurate for procedural-rule dismissals. Hardwick, 126 F.3d at 1313. But we reject this view.
Both before and after AEDPA, 28 U.S.C. § 2254(a) has provided that the writ of habeas corpus may be granted for violation by state courts “of the Constitution or laws or treaties of the United States.” Barefoot’s use of the term “federal” to describe the rights appealable under § 2253 created no ambiguity in the relationship between § 2254 and § 2253; to appeal, petitioners had to make the required “substantial showing” with respect to rights arising under one of the three sources of federal law listed in § 2254. AEDPA’s use of the term “constitutional” in § 2253(c)(2), on the other hand, can, under a strict construction of the text alone, be read to limit the federal rights that may be appealed to those arising under the first of § 2254(a)’s three sources.
We offer no opinion regarding the validity of this distinction. Rather, our point is that the reference to “federal” rights in Barefoot really did not include applications of procedural bars by district courts. Yet, appeals from procedural rulings were allowed pre-AEDPA. See, e.g., Hollis v. Davis, 941 F.2d 1471 (11th Cir.1991) (considering the appeal of district-court conclusions regarding exhaustion and procedural default); Gunn v. Newsome, 881 F.2d 949, 954-63 (11th Cir.1989) (en banc) (considering the appeal of a district-court conclusion regarding abuse of the writ). Our holding today permits nothing more; while the difference between “federal” and “constitutional” might be material with respect to the types of claims raised in the petition, it is not material to the question presented here.
Moreover, as the Third Circuit recently pointed out, pre-AEDPA reasons for appellate review of procedural-rule dismissals have not diminished with the passage of AEDPA. Denying COAs for procedural dismissals
would preclude appellate review of all procedural issues relating to federal ha-beas corpus. The district courts would be left to themselves to develop the law relating to AEDPA’s statute of limitations, the exhaustion requirement, etc., potentially leading to unreviewable contradictions in the law of-, the circuit or the erroneous denial of relief to a petitioner under a sentence of death.
Morris v. Horn, 187 F.3d 333, 340 (3d Cir.1999). Thus, our decision to carry the Barefoot standard forward to deal with procedural-rule dismissals is not only just as consistent with AEDPA’s statutory text as earlier use of Barefoot was with the pre-AEDPA text; it is compelled by the same concerns.
Finally, although AEDPA’s legislative history offers- nothing to either confirm or deny the validity of our holding, see generally S.Rep. No. 104-179 (1995), reprinted in 1996 U.S.C.C.A.N. 924; H.R. Conf. Rep. No. 104-518 (1996), reprinted in 1996 U.S.C.C.A.N. 944, our conclusion is further reinforced by case law. It is consistent with the basic interpretation of AEDPA already adopted by this court, see Hardwick, 126 F.3d at 1313 (“ ‘[T]he AEDPA was intended to codify the Barefoot standard....’ ” (quoting Green v. Johnson, 116 F.3d 1115, 1120 (5th Cir.l997))(alteration in original)), and, importantly, other circuits reaching the question have agreed with the basic proposition that the decision of a district court to dismiss or deny a petition on a procedural ground is properly appealable post-AEDPA. See Morris, 187 F.3d at 339-41; Mickens v. United States, 148 F.3d 145, 147 (2d Cir.1998) (both finding it proper to issue a COA to challenge a district-court conclusion that a petitioner was not entitled to relief under Fed. R. Civ. P. 60(b)); Sonnier v. Johnson, 161 F.3d 94-1, 943-46 (5th Cir.1998); Miller v. N.J. State Dep’t of Corrections, 145 F.3d 616, 617 (3d Cir.1998) (both issuing a COA to challenge a district-court conclusion that a petition was barred under the AEDPA statute of limitations, 28 U.S.C. § 2244(d)); *1366 Whitehead v. Johnson, 157 F.3d 384, 386-87 (5th Cir.1998) (permitting an appeal from the district court’s ruling that the petitioner failed to exhaust state remedies).
We can thus turn to the question whether Henry has satisfied the Barefoot standard. He has. As the magistrate judge’s report and recommendation concluded, Henry presented in his federal petition the same two ineffective-assistance claims he had raised in his state petition. The State concedes this much, but argues, as the district court held, that Henry must exhaust his remedies by requesting a new trial from the Florida appeals court instead of or in addition to the evidentiary hearing he actually requested. Under this relief-centered theory of exhaustion, Henry’s failure to request the identical relief from the state and federal courts renders his state claims unexhausted. Henry’s response, on the other hand, is that he did not need to seek a new trial before the Florida appeals court. He contends that articulating both facts and law substantiating a claim for a new trial is sufficient where the requested evidentiary hearing, if successful, would ultimately result in an order for a new trial.
Precedent does not plainly reject Henry’s argument. The essence of the exhaustion requirement is that a petitioner’s constitutional claims be “fairly presented” to the state courts such that they have “an opportunity to apply controlling legal principles to the facts bearing upon them.” Picard v. Connor, 404 U.S. 270, 275, 277, 92 S.Ct. 509, 512, 513, 30 L.Ed.2d 438 (1971) (quoting Connor v. Picard, 434 F.2d 673 (1970) (quoting United States ex rel. Kemp v. Pate, 359 F.2d 749, 751 (7th Cir.1966))). In Gray v. Netherlands 518 U.S. 152, 163, 116 S.Ct. 2074, 2081, 135 L.Ed.2d 457 (1996), the Supreme Court reiterated that in order to exhaust state remedies, petitioners must do more than present “the state courts only with the facts necessary to state a claim for relief’ and must additionally articulate the constitutional theory serving as the basis for relief. Neither Picard nor Gray, however, reach the question whether a petitioner must not only state a particular constitutional theory and applicable facts but also request a certain form of relief. Furthermore, we cannot draw any inferences from those cases that would lead us to believe Henry’s argument unreasonable. We therefore conclude that reasonable jurists could differ as to whether Henry exhausted his state remedies. Granting a COA is accordingly appropriate.2
*1367III. The Appeal
As stated above, Henry presented the same basic claims-in both law and fact-to the state and federal courts, and he now argues that this is enough to meet Pi-card ’s “fair presentation]” test. The State, on the other hand, contends that Henry’s state-court request for an eviden-tiary hearing rather than a new trial defeats exhaustion. We agree with Henry. Where, as here, state procedure makes it appropriate for a petitioner to request an evidentiary hearing before requesting a new trial, we hold that the difference between a request for an evidentiary hearing in state court and a request for a federal writ under § 2254 (in practical effect here, a request for a new trial) is not enough to render a petitioner’s constitutional claims unexhausted.
Courts have phrased the basic outlines of the Picard test in various ways. Vasquez v. Hillery, 474 U.S. 254, 258, 106 S.Ct. 617, 620, 88 L.Ed.2d 598 (1986), broadly restated the rule to require a petitioner to “present[ ] the substance of his claim to the state courts.” The exact presentation of the claims in the state and federal courts may vary some. See Picard v. Connor, 404 U.S. 270, 277, 92 S.Ct. 509, 513, 30 L.Ed.2d 438 (1971) (“Obviously there are instances in which ‘the ultimate question for disposition’ will be the same despite variations in the legal theory or factual allegations urged in its support. A ready example is a challenge to a confession predicated upon psychological as well as physical coercion.” (citation omitted)). The difference between the two presentations may, however, become significant where legal theories underlying the state and federal claims
(1) ... arise under different federal constitutional provisions (including different clauses in the same constitutional amendment, e.g., the due process and equal protection clauses of the 14th Amendment),
(2) ... arise under the same constitutional provision but are logically distinct or are based on different and unrelated lines of precedent, or
(3)[differ in that] one claim relies on state law while the other relies on possibly distinct federal law, even if the state and federal provisions relied upon are facially identical.... [T]he exhaustion requirement [does not] forbid a prisoner in her federal petition to strengthen or add additional legal support to the legal claim as presented in the state courts.
2 James S. Liebman & Randy Hertz, Federal Habeas Corpus Practice and Procedure § 23.3c, at 891-92 (3d ed.1998) (numerous footnotes to federal cases omitted). Looking to these indicia, it is clear that Henry’s federal and state petitions do not vary significantly. Indeed, the finding of the magistrate judge was that the claims are the same.
Thus, we could find Henry’s claims unexhausted only if we agreed with the State about the relevance of his requesting an evidentiary hearing rather than a new trial from the state court. For two reasons, we cannot agree with the State. First, it has cited no authority for its position. Nor could we find any. See generally Liebman & Hertz, supra, § 23.3c; 17A Charles A. Wright, et al., Federal Practice and Procedure § 4264.3 (1988 & Supp.1999). Second, the “policy of federal-state comity,” Picard, 404 U.S. at 275, 92 S.Ct. at 512, underlying the exhaustion doctrine does not compel the triumph of form over substance that the State’s interpretation would entail. As a general matter, we think that a request for an evidentiary hearing on ineffective-assistance-of-counsel claims is plainly enough an argument that the petitioner has evidence to show his entitlement to a new trial. Indeed, the only reported case we could find confronting the question held implicitly that the difference between a request for an evidentiary hearing and a request for more substantial relief, both premised on the same constitutional claim, is not material to the exhaustion inquiry. *1368 See Watkins v. Callahan, 124 F.2d 1088, 1041 (1st Cir.1984) (holding, without even explicitly addressing the change in the procedural relief sought, that Watkins fairly presented his Miranda claims to the state court where his state-court allegation was a per se Miranda violation entitling him to exclude his confession while his federal court allegation was an Edwards v. Arizona, 451 U.S. 477, 101 S.Ct. 1880, 68 L.Ed.2d 378 (1981), violation requiring an evidentiary hearing in the district court).
Nevertheless, we recognize that if state procedure explicitly demanded more of a petitioner, a request for a hearing might not be enough. Florida’s rule, however, makes no such demand. Under Rule 3.850, it is the trial judge who determines how much procedural attention a petition warrants. See Fla. R. Crim. P. 3.850(d). Henry’s state-court appeal, which requested only the evidentiary hearing denied by the trial judge, was therefore appropriately modest. It asked for the most he could reasonably have expected from the appeals court — an order vacating and remanding for an evidentiary hearing. Exhaustion should not be construed to mandate more.
IV. Conclusion
Having reviewed Henry’s application for a COA to appeal the district court’s determination that Henry failed to exhaust his constitutional claims in state court, we uphold the grant of a COA. In light of the briefs submitted and oral argument on the issue, we further conclude that Henry did exhaust his state remedies. We therefore vacate the district court’s denial of Henry’s petition and remand for further proceedings.
COA GRANTED; VACATED and REMANDED.