In 1980, Delma Banks, Jr. was convicted in Texas state court of capital murder and sentenced to death. After pursuing his state remedies, Banks filed for federal ha-beas relief in 1996 (before the effective date of the Antiterrorism and Effective Death Penalty Act (AEDPA)). Among the numerous issues raised, he claimed: for two of the State’s witnesses, the prosecution withheld material exculpatory impeachment evidence, in violation of Brady v. Maryland, 373 U.S. 83, 83 S.Ct. 1194, 10 L.Ed.2d 215 (1963). The district court denied relief for Banks’ conviction, but granted it for the sentence. Because it had not been properly pleaded, the district court refused to rule on Banks’ Brady claim based on the prosecution’s suppression of a pre-trial interview transcript for witness Charles Cook; that transcript had not been produced until the federal habeas proceeding and had been admitted in evidence at the subsequent evidentiary hearing.
On appeal, in a 78-page opinion addressing numerous issues, we vacated the habe-as relief for the sentence and denied a certificate of appealability (COA) for the guilt phase concerning, inter alia: whether Banks’ Cook-transcript Brady claim was properly pleaded; or whether, in the alternative, it had been tried by consent of the parties pursuant to Federal Rule of Civil Procedure 15(b) (amendment of pleadings to conform to evidence “[w]hen issues not raised by the pleadings are tried by express or implied consent of the parties”). Banks v. Cockrell, No. 01-40058, 48 Fed.Appx. 104 (5th Cir.2002) (unpublished).
The Supreme Court held: Banks was entitled to habeas relief for the sentence; and, for the Cook-transcript Brady claim, a COA “should have issued” “[a]t least as to the application of Rule 15(b)” to the district court evidentiary hearing. Banks v. Dretke, 540 U.S. 668, 124 S.Ct. 1256, 1280, 157 L.Ed.2d 1166 (2004).
Because the Supreme Court granted that COA, we address: whether Rule 15(b) applies to issues raised in a pre-AEDPA district court evidentiary hearing; and, if it does, how the Rule applies here. Because the Rule applies and the district court has not addressed its application to the Cook-transcript Brady claim, we REMAND to district court.
I.
The Supreme Court’s remand concerns only the discrete procedural issue of whether Rule 15(b) applies to claims tried by consent in pre-AEDPA federal habeas proceedings. (The Court stated: “Banks’ case provides no occasion to consider Rule 15(b)’s application under the AEDPA regime”. Id. at 1280 n. 20). The facts and procedural history for Banks’ underlying state conviction and post-conviction proceedings have been exhaustively addressed *275both by this court and the Supreme Court. See Banks, 124 S.Ct. 1256; Banks, No. 01-40058, 48 Fed.Appx. 104. Accordingly, we recite only the facts and fairly complex procedural history relevant to the Supreme Court’s COA-grant at hand.
In 1980, Banks was convicted for the murder of Richard Whitehead in Texas state court and sentenced to death. Officers investigating Richard Whitehead’s death had turned their attention to Banks when they learned that Richard Whitehead had been seen with him on 11 April 1980 near Nash, Texas; Richard Whitehead’s body was found on 14 April. On 28 April, after receiving a tip from a confidential informant that Banks was traveling to Dallas, Texas, to meet an individual and obtain a weapon, officers followed Banks to Dallas, where he visited a residence. As Banks was leaving Dallas, officers stopped his vehicle and found a handgun; officers then returned to the residence Banks had visited and interviewed Charles Cook there. WTiile at the residence, officers recovered a second handgun; Cook told the officers that Banks had left that second handgun with him days earlier. Tests identified the second handgun as the Whitehead murder weapon.
Prior to trial, Banks’ attorney sought information concerning the identity of the informant who had told officers that Banks would be traveling to Dallas, but the prosecution claimed the information was privileged. The prosecution eventually advised Banks’ counsel that “[the State] will, without necessity of motions provide you with all discovery to which you are entitled”.
During the guilt phase of Banks’ trial, witnesses testified to seeing Banks and Richard Whitehead together in a green Mustang on 11 April (shortly before Richard Whitehead’s death). Cook testified: Banks arrived in Dallas in a green Mustang at about 8:15 a.m. on 12 April and stayed until 14 April; and, during this period, Banks admitted to having “kill[ed] the white boy for the hell of it and take[n] his car and come to Dallas”. Banks, 124 S.Ct. at 1264. Cook testified further that Banks then abandoned the Mustang and left Dallas by bus. On cross-examination, Cook stated three times that he had not talked with anyone about his testimony. (As discussed infra, it was discovered in the course of this habeas proceeding, however, that Cook had at least one “pretrial practice session”, at which officers and prosecutors coached him about his trial testimony.) Cook did not testify at the penalty phase.
At the guilt phase, another of the State’s key witnesses, Robert Farr, corroborated Cook’s account. Farr also testified against Banks at the penalty phase. (It was revealed during this federal habeas proceeding that Farr had been the confidential informant who told officers about Banks’ intention to go to Dallas and that Farr had been paid for that information.)
After pursuing available state remedies, Banks filed the instant federal habeas application in March 1996, asserting, inter alia, a Brady claim based on the prosecution’s failure to produce exculpatory evidence, including “information that pointed to another suspect in the murder, information that linked prosecution star witness Charles Cook to Robert Farr ... and information that would have revealed Robert Farr as a police informant and Mr. Banks’ arrest as a ‘set-up’ ”. (Emphasis added.) Banks also claimed: “prosecutors’ actions in concealing from the jury Cook’s enormous incentive to testify in a manner favorable to the State require that this Court reverse Mr. Banks’ conviction and sentence”; and “[t]he prosecution’s failure to disclose that Cook stood to profit so enormously by his testimony, narrowly evading a possible life term in prison, *276requires the reversal of Mr. Banks’ conviction and sentence”. (Emphasis added.) It appears that Cook’s alleged “incentive to testify in a manner favorable to the prosecution” is the “deal”-with-the-proseeution referred to by the Supreme Court, as quoted infra. E.g., Banks, 124 S.Ct. at 1269.
The magistrate judge ordered an evi-dentiary hearing to address, inter alia, Banks’ claims that the State had withheld “crucial exculpatory and impeaching evidence” concerning Cook and Farr. Banks v. Johnson, No. 5:96-CV-353, at 1 (E.D.Texas 5 March 1999). Prior to that hearing, the magistrate judge ordered the prosecution to produce its files from Banks’ trial. Discovered in those files was a 74-page transcript of a pre-trial interview of Cook, conducted by law enforcement officials and prosecutors in September 1980, shortly before trial.
■The Cook transcript revealed
the State’s representatives had closely rehearsed Cook’s testimony. In particular, the officials told Cook how to reconcile his testimony with affidavits to which he had earlier subscribed recounting Banks’s visit to Dallas. (‘Tour [April 1980] statement is obviously screwed up.”); (“[T]he way this statement should read is that ... ”); (“[L]et me tell you how this is going to work.”); (“That’s not in your [earlier] statement”). Although the transcript did not bear on Banks’s claim that the prosecution had a deal with Cook, it provided compelling evidence that Cook’s testimony had been tutored by Banks’s prosecutors.
Banks, 124 S.Ct. at 1269 (citations omitted; emphasis added). Again, the Supreme Court’s discussion of the alleged “deal” between Cook and the prosecution appears to be in reference to Banks’ claim in his federal habeas petition that Cook had an incentive to testify favorably for the prosecution.
The Cook-interview transcript was listed in Banks’ identification of exhibits to be introduced at the district court evidentiary hearing. At that hearing, Banks’ counsel introduced the transcript in evidence without objection and questioned the assistant district attorney at the time of trial about whether, at trial, the prosecution should have allowed Cook to testify that, pre-trial, he had not talked to anyone about his testimony (the transcript proved otherwise). Banks’ post-evidentiary-hearing brief on an unrelated issue noted that discovery “dislodged” the Cook-interview transcript and claimed the transcript demonstrated that key trial testimony was coached and inaccurate.
Banks’ proposed findings of fact and conclusions of law for the magistrate judge (for the report and recommendation to the district judge) referenced the Cook transcript several times. Inter alia, Banks: asserted that, by suppressing the transcript, prosecutors breached their promise of full disclosure; described the withholding of the transcript; proposed the court find the transcript was in possession of the prosecution pre-trial, but not produced to counsel until habeas discovery in 1999; and suggested the court conclude that Banks’ trial was rendered fundamentally unfair by the transcript’s suppression.
The magistrate judge recommended granting habeas relief on Banks’ Brady claim concerning Farr, but denying relief on the Brady claim concerning Cook’s alleged deal with the prosecution. The report and recommendation did not mention, however, the suppression of the Cook-interview transcript.
Banks objected to the report and recommendation because, inter alia, it failed to mention the transcript’s non-production; *277because of its suppression, Banks claimed he was entitled to relief from his conviction. The district court adopted the magistrate judge’s recommendation and granted habeas relief for the penalty phase of Banks’ trial, but denied relief for the guilt phase. In doing so, the district court overruled some of Banks’ objections to the magistrate judge’s report and recommendation; however, the district court did not address Banks’ objection to the magistrate judge’s failure to address the suppression of the Cook-interview transcript.
Banks moved to amend the judgment on the basis that the suppression of the Cook-interview transcript was material, but the issue had not been addressed by either the magistrate judge or district judge. In response to that motion, the State contended, for the first time, that a Brady claim based on the suppression of the Cook transcript was not before the court because it was not properly pleaded under Rule 15(a) (amendments generally). Banks replied that the Brady claim in his petition, which alleged the State withheld impeachment evidence regarding Cook, was sufficient to state such a claim and the Cook-interview transcript was merely evidence supporting it. (Banks’ petition had mentioned Cook’s testimony after claiming the prosecution failed to turn over material exculpatory evidence, in violation of Brady.) Banks further contended that “the issue of whether trial prosecutors suppressed material impeachment evidence concerning Charles Cook [was] tried at the [district court] Evidentiary Hearing” (emphasis added); but, he did not specifically rely on Rule 15(b) (amendment of pleadings to conform to the evidence “[w]hen issues not raised by the pleadings are tried by express or implied consent of the parties”). The district court denied the motion to amend the judgment, holding: Banks raised the Cook-transcript Brady claim for the first time in the findings of fact and conclusions of law proposed for the magistrate judge; and this was not proper pleading under Rules 15(a) or (d) (supplemental pleading).
In his COA-request in district court, Banks claimed, inter alia, that, pursuant to the governing standard for whether to grant a COA, jurists of reason could debate whether the district court correctly held the Cook-transcript Brady claim was not properly before the district court. Banks contended the claim was properly pleaded; and, for the first time, he relied alternatively on Rule 15(b). The district court denied a COA on the Cook-transcript Brady claim: it ruled the claim was not properly raised in the first instance; but, although it noted Banks’ reliance on Rule 15(b), it did not address whether the Cook-transcript Brady claim had been tried by express or implied consent of the parties.
The State appealed the habeas relief granted for the sentence; Banks cross-appealed, requesting a COA on, inter alia: “Whether the court below erred when it refused to review the merits of the due process claim concerning the suppression of a lengthy pretrial statement of the state’s key witness [Cook] because Banks did not formally amend the petition after disclosure of the statement”. In his appellate brief, in support of that COA-request, Banks again contended: his Cook-transcript Brady claim was properly pleaded in the first instance; and, in the alternative, a claim based on the transcript was tried by consent of the parties and, therefore, was properly pleaded under Rule 15(b). The State responded, inter alia, that, “although there was a federal evidentiary hearing, there was certainly never any ‘trial’ regarding the instant Brady allegations”. It also claimed, inter alia, that an evidentiary hearing did not waive exhaustion or procedural default defenses.
*278For this COA-request, we held the district court had correctly determined that Banks did not properly plead the Cook-transcript Brady claim because: after discovering the transcript, Banks should have sought leave to amend his petition; and issues first raised in objections to a magistrate judge’s report and recommendation are not properly before the district court. Banks, No. 01-40058, at 52, 48 Fed.Appx. 104; see United States v. Armstrong, 951 F.2d 626, 630 (5th Cir.1992). Concerning the alternative Rule 15(b) basis offered in support of the COA-request, we stated: “Banks has not pointed to any authority supporting his contention that, for Rule 15 purposes, an evidentiary hearing equates with a trial”. Banks, No. 01-40058, at 52, 48 Fed.Appx. 104, (emphasis added). Accordingly, we denied a COA, holding it was not debatable among jurists of reason whether the district court was correct in denying Banks’ motion to amend the judgment, the denial of which is reviewed for abuse of discretion. Id.
Before the Supreme Court, however, the State changed its position concerning Rule 15(b) and “eoncede[d] ... that the question whether Rule 15(b) extends to habeas proceedings is one ‘jurists find ... debatable’”. Banks, 124 S.Ct. at 1279. The Court reversed our COA — denial for the Cook — transcript Brady claim: “We see no reason why an evidentiary hearing should not qualify [as a trial for Rule 15(b) purposes] so long as the [State] gave ‘any sort of consent’ and had a full and fair ‘opportunity to present evidence bearing on th[e] claim’s resolution’ ”. Id. at 1280 (citing Withrow v. Williams, 507 U.S. 680, 696, 113 S.Ct. 1745, 123 L.Ed.2d 407 (1993)). The Court held that, “at least as to the application of Rule 15(b)”, a COA “should have issued”. Id.
II.
The Supreme Court’s COA-holding prompts several procedural questions: the scope of its COA-grant; whether Rule 15(b) applies to pre-AEDPA federal habeas evidentiary hearings; and, if it does, how it applies here. To assist with resolution of these issues, we obtained supplemental briefing from the parties.
A.
Because Banks’ federal petition was filed pre-AEDPA, that Act is not applicable to his claims. Id. at 1270 n. 9 (citing Lindh v. Murphy, 521 U.S. 320, 336-37, 117 S.Ct. 2059, 138 L.Ed.2d 481 (1997)). He was required, however, to obtain a COA, pursuant to AEDPA, in order to appeal a denied claim. See Green v. Johnson, 116 F.3d 1115, 1120 (5th Cir.1997); 28 U.S.C. § 2253(c)(1)(A).
Banks contends the Supreme Court’s COA-grant encompasses both whether his Cook-transcript Brady claim was properly pleaded in the first instance and whether, in the alternative, that claim was tried by consent of the parties. Although Banks has consistently urged (district court, here, and Supreme Court) that his Cook-transcript Brady claim was properly pleaded, the Supreme Court’s COA-grant does not encompass that issue. Concerning the COA, the Court’s opinion almost exclusively addressed Rule 15(b)’s application to pre-AEDPA federal habeas evidentiary hearings and, as quoted in part above, held:
To obtain a certificate of appealability, a prisoner must “demonstrat[e] that jurists of reason could disagree with the district court’s resolution of his constitutional claims or that jurists could conclude the issues presented are adequate to deserve encouragement to proceed further.” Miller-El v. Cockrell, 537 U.S. 322, 327, 123 S.Ct. 1029, 154 L.Ed.2d 931 (2003). At least as to the *279application of Rule 15(b), this case surely fits that description. A certificate of appealability, therefore, should have issued.
Banks, 124 S.Ct. at 1280 (emphasis added).
We denied a COA on whether Banks’ Cook-transcript Brady claim was properly pleaded in the first instance; because the Supreme Court did not hold to the contrary, our decision on that issue remains the law of the case. Accordingly, the remand from the Supreme Court is limited to whether Rule 15(b) applies to pre-AED-PA federal habeas evidentiary hearings and, if it does, its effect here.
B.
Rule 15 governs amendments to, and supplemental, pleadings. Pursuant to the Supreme Court’s COA-grant, we decide de novo whether Rule 15(b) applies to pre-AEDPA federal habeas proceedings. See, e.g., Mann v. Scott, 41 F.3d 968, 974 (5th Cir.1994) (noting our plenary review for questions of federal law in habeas proceedings).
Concerning amendments to the pleadings to conform to the evidence, Rule 15(b) states:
When issues not raised by the pleadings are tried by express or implied consent of the parties, they shall be treated in all respects as if they had been raised in the pleadings. Such amendment of the pleadings as may be necessary to cause them to conform to the evidence and to raise these issues may be made upon motion of any party at any time, even after judgment; but failure so to amend does not affect the result of the trial of these issues.
Fed.R.Civ.P. 15(b)(emphasis added). As quoted above, that part of the Supreme Court’s opinion granting the COA has provided guidance on whether Rule 15(b) applies to pre-AEDPA federal habeas evi-dentiary hearings: ‘We see no reason why an evidentiary hearing should not [equate with a trial for Rule 15(b) purposes] so long as the [State] gave ‘any sort of consent’ and had a full and fair ‘opportunity to present evidence bearing on the claim’s resolution’ ”. Banks, 124 S.Ct. at 1280 (quoting Withrow, 507 U.S. at 696, 113 S.Ct. 1745).
In so stating, the Court noted it had twice referenced Rule 15(b)’s application in federal habeas proceedings: Withrow, 507 U.S. at 696, 113 S.Ct. 1745 (assuming, without analysis, that Rule 15(b) applied); Harris v. Nelson, 394 U.S. 286, 294 n. 5, 89 S.Ct. 1082, 22 L.Ed.2d 281 (1969)(noting use of Rule 15(b) in habeas proceedings is noncontroversial). The Court doubted that Rule 15(b)’s application “would undermine the State’s exhaustion and procedural default defenses” under the pre-AEDPA scheme. Banks, 124 S.Ct. at 1280. (As partly discussed above, although our prior opinion noted that the State raised these defenses against application of Rule 15(b), our COA-denial did not require addressing that point. See Banks, No. 01-40058, at 52, 48 Fed.Appx. 104.)
In addition, the State concedes that, although the Supreme Court has not expressly held Rule 15(b) applies to pre-AEDPA federal habeas evidentiary hearings, our court has applied that Rule in such proceedings. For example, Mosley v. Dutton, 367 F.2d 913, 916 (5th Cir.1966), considered issues that had been tried by the parties’ consent in a habeas proceeding as if raised in the pleadings (citing Rule 15(b)). See also Streeter v. Hopper, 618 F.2d 1178, 1180 (5th Cir.1980) (reviewing grant of habeas relief and considering one of the issues litigated by parties’ consent) (citing Rule 15(b)). We have also noted the potential application of Rule 15(b) to pre-AEDPA habeas proceedings in in*280stances where the Rule was ultimately not invoked to amend the petition. See James v. Whitley, 926 F.2d 1433, 1435 n. 3 (5th Cir.1991) (noting claims may have been tried by consent of parties at federal habe-as evidentiary hearing pursuant to Rule 15(b), but not reaching issue); Robinson v. Wade, 686 F.2d 298, 304 n. 11 (5th Cir.1982) (holding “Federal Rules of Civil Procedure govern amendments of petitions for habeas corpus”, and noting certain exceptions, including Rule 15(b), to the requirement that claims in habeas proceedings can be added only by amendment).
In Banks’ pre-AEDPA federal habeas evidentiary hearing, the Cook-transcript was in evidence; it had not been produced by the State until during this habeas proceeding. Moreover, the State does not claim an exhaustion or procedural bar defense to the Cook-transcript Brady claim. Accordingly, on this record, Rule 15(b) applies to the Cook-transcript Brady claim as addressed in Banks’ evidentiary hearing.
C.
The State contends that, although Rule 15(b) may generally apply to issues tried by consent in a habeas evidentiary hearing, it does not apply here because, in district court, Banks contended only that the Cook-transcript Brady claim was tried by express consent of the parties and did not rely on implied consent. In support, the State cites Banks’ COA-request in district court (the first time Banks cited Rule 15(b)); that request quoted the text of Rule 15(b) regarding trial by express or implied consent and then stated: “This issue of the state’s suppression of impeachment material concerning Charles Cook was ‘expressly tried’ at the ... evidentiary hearing”. (Emphasis added.) That COA-request in district court also notes: the Cook transcript was admitted in evidence without objection; and Banks’ counsel questioned the prosecutor and other witnesses extensively about its content.
Banks’ COA-request to this court claimed: “The district court erred in failing to adjudicate [Banks’ claim that] the prosecution’s suppression of Charles Cook’s lengthy pretrial statement withheld material impeachment evidence and violated due process”. For support, Banks cited, inter alia, Rule 15(b) and contended the State was on notice he was asserting a Cook-transcript Brady claim.
1.
The State contends that, because Banks did not explicitly raise “implied consent” in district court, the implied consent issue at hand cannot be considered for the first time on appeal. See Johnson v. Puckett, 176 F.3d 809, 814 (5th Cir.1999) (holding contention not raised by habeas petitioner in district court cannot be considered for the first time on appeal from that court’s denial of habeas relief); Muniz v. Johnson, 114 F.3d 43, 45 (5th Cir.1997) (“A district court must deny the COA before a petitioner can request one from this court.”) We disagree that Banks’ COA-request in district court relied exclusively on the express consent portion of Rule 15(b).
First, Banks quoted the language of Rule 15(b) which addresses both express and implied consent. Second, although the COA-request in district court claimed the issue of the State’s suppression of the Cook transcript was “expressly tried”, we do not understand that to mean Banks was referring to express consent. Banks did not contend the State had expressly consented to trial of the Cook-transcript Brady claim; instead, he stated the claim had been “expressly tried”. At issue is whether the trial of the claim was based on the State’s implied consent. *281Moreover, Banks’ reliance on the admission of the transcript in evidence without objection and the questioning of the trial prosecutor about the transcript supports implied, rather than express, consent. Accordingly, because Banks relied in district court on the Cook-transcript Brady claim’s being tried by implied consent, we consider this issue. (In any event, even if, ar-guendo, Banks had not relied on implied consent in district court, the Supreme Court’s COA-grant addressed implied consent and cured Banks’ alleged default.)
2.
We decline, however, to decide in the first instance whether that Brady claim ivas tried by implied consent of the parties. The State concedes that, if the issue of implied consent is properly before us, we should remand because the district court never addressed it.
Although on 6 June 2004 we denied Banks’ motion to remand to district court for factfinding on this issue, we did so in order to obtain supplemental briefing to consider further this and other questions relevant to the Supreme Court’s remand. In the light of that briefing and related factors commending the district court’s considering the consent question in the first instance, we conclude that remand to the district court is required in order for it (1) to determine whether Banks’ Cook-transcript Brady claim was tried by implied consent of the parties; and (2) if it was, to decide that claim.
III.
For the foregoing reasons, this matter is REMANDED to district court for further proceedings consistent with this opinion.
REMANDED.