#### Antonio Don MILTON, Petitioner-Appellant, v. David MILLER, Respondent-Appellee.

No. 15-6069.

United States Court of Appeals, Tenth Circuit.

Feb. 9, 2016.

*1254John T. Carlson, Office of the Federal Public Defender, Denver, CO, for Petitioner-Appellant.

Jay Schniederjan, Office of the Attorney General for the State of Oklahoma, Oklahoma City, OK; Joshua L. Lockett, Office of the Attorney General for the- State of Oklahoma, Oklahoma City, OK, for Respondent-Appellee.

Before MATHESON, MURPHY, and PHILLIPS, Circuit Judges.

PHILLIPS, Circuit Judge.

Antonio Don Milton, an Oklahoma state prisoner, requests a certifícate of appeala-bility (COA) to appeal the district court’s denial of his 28 U.S.C. § 2254 petition for habeas relief. Exercising jurisdiction under 28 U.S.C. §§ 1291 and 2253(a), we deny Milton’s request for a COA.

I. BACKGROUND

We have previously detailed Milton’s history in Oklahoma state courts and the federal district court. *See Milton v. Miller,*744 F.3d 660, 663-68 (10th Cir.2014).1 Milton’s case returns to us after we reversed the district court’s denial of his habeas petition solely regarding Milton’s ineffective-assistance-of-appellate-counsel claim and remanded for an evidentiary hearing on a narrow factual dispute, which, once resolved, would assist the district court in better assessing the merits of Milton’s remaining ineffective-assistance claim. *See id.*at 673. With evidence from the hearing now available to us, we have the necessary facts to assess Milton’s claim. Because the evidentiary hearing revealed new facts not known to courts that have previously addressed Milton’s post-conviction claims, we recount Milton’s journey through the criminal-justice system for the sake of clarity and coherence with our earlier opinion.

A. State Court Proceedings

In 2007, Milton was prosecuted in two separate cases pending simultaneously before a state district court. One included a charge for Milton’s trafficking in .cocaine base (crack cocaine),2 while the other case concerned his involvement in a drive-by shooting.3 Separate attorneys represented Milton in each case: Jacob Benedict, a public defender, represented Milton in the *1255drug-trafficking case until Michael Arnett took over after the preliminary hearing; Joe Reynolds, a private attorney, represented Milton in the drive-by-shooting case. Because Milton had two earlier felony drug-trafficking convictions, the crack-cocaine-trafficking charge mandated life without parole upon conviction. *See*Okla. Stat. tit. 63, § 2 — 415(D)(3) (2004) (“If the person has previously been convicted of two or more violations of this section or any provision of the Uniform Controlled Dangerous Substances Act which consti-tútes a felony, or a combination of such violations arising out of separate and distinct transactions, [his sentence shall be a term of imprisonment of] life without parole.”).

The State extended Milton at least one plea offer that covered at least one of Milton’s two cases. The parties have disputed the terms of the offered plea deal (or deals) throughout Milton’s pretrial and post-conviction proceedings. But Milton ultimately rejected the offered plea deal(s) and went to trial in the drug-trafficking case. He was convicted of the crack-cocaine-trafficking charge and sentenced to the mandatory term of life without parole. After this, the State let the drive-by-shooting case lapse, leaving the court to dismiss it for lack of prosecution.

On direct appeal, Katrina Conrad-Le-gler represented Milton. The Oklahoma Court of Criminal Appeals (OCCA) affirmed all of Milton’s convictions and sentences, including the drug-trafficking conviction with its mandatory life-without-parole sentence. Later, Milton filed a pro se application for post-conviction relief and requested an evidentiary hearing in Oklahoma state district court. Relevant here, Milton argued “that his appellate counsel rendered ineffective assistance by failing to assert on direct appeal that Milton’s trial counsel was ineffective for failing to inform Milton of a plea-bargain offer made by the prosecution prior to the preliminary hearing.” *Milton,*744 F.3d at 664.

Milton’s ineffective-assistance claim had some basis in the record. At a pretrial hearing in the drug-trafficking case, Judge Twyla Mason Gray mentioned that, sometime before his preliminary hearing, Milton had rejected an offered plea deal providing for a 23-year sentence in the drug-trafficking case.4 Upon hearing Judge Gray say this, Milton told his counsel at the time of trial, Arnett, who then told Judge Gray, that Milton had never heard about a 23-year offer. In response to the confusion, the prosecutor at the pretrial hearing, Ashley Altshuler, referenced the notes of Benjamin McGoldrick, the prosecutor who handled the case until leaving the office sometime after December 2007. McGoldrick’s notes reflected that on the day of a preliminary-hearing conference,5 he offered Milton a plea deal of 25 years’ incarceration in the drug-trafficking case, to run concurrently 'with 20 years’ incarceration in the drive-by-shooting case (25/20 Deal).6 Now better informed, *1256Judge Gray declared irrelevant any plea deals McGoldrick had offered Milton before the preliminary hearing because those deals had expired. Given this factual background, Milton argued that his direct-appeal counsel had ineffectively assisted him by not raising his trial counsel’s ineffectiveness in not telling Milton about the 23-year offer Judge Gray had mentioned.

The State opposed Milton’s application for post-conviction relief, relying principally on an affidavit Jacob Benedict (Milton’s public defender) submitted, when the State supposedly had offered Milton the 23-year deal. In his affidavit, Benedict recounted two plea deals the State had offered to Milton before the preliminary hearing. The plea deals contained essentially the same terms, differing only on the date they were communicated: Milton was offered 20-year concurrent sentences in the drug-trafficking case and the drive-by-shooting case (20/20 Deal). The affidavit noted that McGoldrick originally offered the 20/20 Deal sometime before the preliminary-hearing date, and that McGol-drick also offered the same deal just before the hearing began. According to Benedict’s affidavit, Milton rejected the offers, and the parties proceeded with the preliminary hearing.

Based partly on this information, the state district court denied Milton’s application for post-conviction relief on his ineffective-assistance-of-appellate-counsel claim, concluding that “[tjhere is nothing submitted in the record which indicates that appellate counsel’s performance rendered the result unreliable or the proceeding fundamentally unfair.” R. vol. 1 at 214. On appeal, the OCCA affirmed, citing *Strickland v. Washington,*466 U.S. 668, 687, 104 S.Ct. 2052, 80 L.Ed.2d 674 (1984), and holding as follows:

> [I]n order to prevail on his claim of ineffective assistance of appellate counsel, [Milton] must establish counsel made errors so serious the performance was deficient, and that the deficient performance deprived him of an appeal whose results are reliable and fair. The fact appellate counsel fails to recognize or raise a claim, *regardless of merit,*is not sufficient alone to establish ineffective assistance of counsel, or to preclude enforcement of a procedural default. We [find Milton] has not established appellate counsel’s performance was deficient, or that the result of his appeal was not reliable and fair.

R. vol. 1 at 236-37 (citation omitted) (emphasis added). Thus, as Milton’s application for post-conviction relief proceeded through Oklahoma courts, the courts considered conflicting evidence about offers for the 20/20 Deal, the 25/20 Deal, and a supposed 23-year deal.7

The timing, communication, and existence of each of these deals matter. Obviously, had McGoldrick offered Milton the 20/20 Deal minutes before the preliminary hearing, Milton could not have suffered prejudice from any earlier failure by his counsel to communicate a less favorable 23-year offer. But had McGoldrick offered Milton the 25/20 Deal before the preliminary hearing, Milton could have suffered prejudice if his counsel failed to communicate a more favorable 23-year deal before the preliminary hearing. But the state courts denied Milton relief without ever determining whether McGoldrick *1257had offered a 23-year deal and, if so, whether Milton’s counsel had told Milton about it.

B. Federal Habeas Proceedings

Milton next filed a pro se habeas petition under 28 U.S.C. § 2254 in the United States District Court for the Western District of Oklahoma. Milton alleged various claims for relief, including the same ineffective-assistanee-of-appellate-counsel claim he had argued in the state courts:

> Appellate counsel, Katrina Conrad-Le-gler, rendered ineffective assistance by failing to raise in [Milton]’s direct appeal the following sub-proposition[ ] of trial counsel’s deficienc[i]es: ... Trial attorney, Joe Reynolds, rendered ineffective assistance by failing to inform [Milton] of a (pre-preliminary hearing) plea-bargain offer of 23 years on all counts until the day set for trial, and well after the plea offer had been withdrawn.

R. vol. 1 at 29 (capitalization omitted). The magistrate judge assigned to Milton’s case issued a report recommending that the district court deny Milton’s habeas petition in its entirety.

In .concluding that Milton’s ineffective-assistance claim lacked merit, the magistrate judge referenced Benedict’s affidavit, the same one that the state courts had relied upon to deny Milton’s claim. Milton argued that the 20/20 Deal referenced in the affidavit was a different plea deal than the one Milton had complained of in his habeas petition (i.e., the 23-year deal). The magistrate judge interpreted Milton’s argument as conceding the truth of the affidavit. From this, the magistrate judge concluded that Milton could not have suffered any prejudice from not hearing about the 23-year offer since he had already rejected the more favorable 20/20 Deal. Accordingly, the magistrate judge recommended that the district court deny Milton’s petition because he had failed to show any prejudice.

Milton objected to the magistrate judge’s report and recommendation. He conceded that he had been offered a 20-year plea deal in the drive-by-shooting case but denied receiving any offers in the drug-trafficking case — whether the purported offer was the 25/20 Deal or the 23-year deal. He claimed that he first heard of both the 25/20 Deal and the 23-year deal when Altshuler and Judge Gray discussed the pre-preliminary-hearing plea offers on the eve of trial. Therefore, Milton argued that either Benedict was lying in his affidavit about having conveyed to him the offered 20/20 Deal or that Benedict had confused the drug-trafficking case with the drive-by-shooting case. Milton noted that “[t]he issue” was that no one had “informed [him] of any pre-prelimi-nary hearing plea offer in [the drug-trafficking case], and as a direct result, rather than serving a twenty-five (25) year sentence with all counts running concurrently,” he was serving a life sentence without the possibility of parole. R. vol. 1 at 894. From this, he contended that he had been “prejudiced by trial counsel’s failure to timely inform him of the State’s pre-pre-liminary hearing plea offer of twenty-five (25) years in [the drug-trafficking case].” *Id.*The confusion over the offers for the 20/20 Deal, the 25/20 Deal, and the 23-year deal persisted. Was Milton now arguing that his trial counsel had failed to communicate the 25/20 Deal and the 23-year deal he mentioned in his habeas petition? If so, the record does not show that he expressed surprise at the pretrial hearing after Altshuler told Judge Gray about the pre-preliminary-hearing plea offer of the 25/20 Deal.

Leaving Milton’s objections unaddressed, the district court simply adopted the magistrate judge’s report and recommendation. The district court declined to *1258grant a COA, but we later granted Milton’s pro se request for a COA on his ineffective-assistance-of-appellate-eounsel claim and appointed Milton counsel to assist with his appeal.

In *Milton,*we concluded that the OCCA’s ineffective-assistance analysis was contrary to clearly established federal law and that Milton had overcome the bar that 28 U.S.C. § 2254(d)(1) imposed. *Milton,*744 F.3d at 669-70. Specifically, we concluded that the OCCA “rendered meaningless” its prejudice analysis under *Strickland*“[b]y ignoring the merits of the underlying predicate claim in assessing appellate counsel’s performance.” *Id.*at 670. In this regard, we held that the OCCA had “deviated from the controlling federal standard.” *Id.*(quoting *McGee v. Higgins,*568 F.3d 832, 839 (10th Cir.2009)). With § 2254(d)(l)’s bar no longer in play, we then reviewed de novo Milton’s *Strickland*claim.

Applying the two-pronged *Strickland*framework, we first concluded that Milton’s appellate counsel, upon reviewing Milton’s trial transcripts, should have seen and raised as an issue that Milton’s trial attorney had “failed to promptly and meaningfully convey to Milton the existence of a plea offer made by the prosecution at some point” before the preliminary hearing. *Id.*at 671. The trial counsel’s failure, we concluded, would have been “inconsistent with prevailing professional norms and [would have given] rise to a viable claim of ineffective assistance of trial counsel.” *Id.*We therefore held that “[b]y failing to discover and raise the issue [of trial counsel’s ineffectiveness] on direct appeal, Milton’s appellate counsel clearly performed deficiently.” *Id.*

In addition, the *Milton*court considered under *Strickland’s*second prong “whether Milton was prejudiced by his appellate counsel’s deficient performance.” *Id.*We concluded that the state courts and the federal district court had erred by finding, based solely on Benedict’s affidavit and in the face of conflicting evidence, that Milton had suffered no prejudice from his appellate counsel’s ineffective assistance. We noted that prejudice depended on whether Milton’s counsel had failed, to convey to Milton any plea offer in the drug-trafficking case: “Assuming, for purposes of argument, that Milton is truthfully alleging that he was not informed of any pre-pre-liminary-hearing plea offer, and that he would have accepted such offer had he been timely informed of it, that is clearly sufficient to establish prejudice....” *Id.*at 672.

We concluded that Milton was entitled to a federal evidentiary hearing to resolve this factual dispute because the appellate record did not give us sufficient information to do so.8 The evidentiary hearing would bring forth crucial facts: either (1) that Milton’s trial counsel had indeed failed to communicate a favorable plea deal, which likely would satisfy *Strickland’s*prejudice prong, or (2) that Milton’s trial counsel had communicated the most *1259favorable plea deal, meaning Milton’s ineffective assistance claim would fail to satisfy *Strickland’s*prejudice prong. As explained below, the evidentiary hearing produced facts that did not fit squarely into either category.

C. The Evidentiary Hearing

On remand, the district court held an evidentiary hearing to resolve the factual dispute regarding the nature of Milton’s plea offers. We recount the testimony relevant to this appeal.9

*1. McGoldrick’s Testimony*

The testimony of Benjamin McGoldrick, the prosecutor assigned to both of Milton’s cases until McGoldrick left the office sometime after December 2007, produced three important facts.

First, McGoldrick testified that he never communicated a 23-year plea deal to either Benedict or Reynolds, notwithstanding his case-file notes referencing a possible plea offer for a 23-year sentence in the drug-trafficking case and a concurrent 23-year sentence in the drive-by-shooting case (23/23 Deal).10 Importantly, these notes about the-possible 23/23 Deal are dated December 18, 2007-well after the October 30, 2007 preliminary hearing. McGoldrick testified that he wrote the notes about the possible 23/23 Deal as a potential recommendation if Milton’s attorneys agreed to resolve the ease without trial at a pretrial conference scheduled for the following day, December 19, 2007. But critically, McGol-drick testified that he in fact never communicated an offer for the 23/23 Deal to either of Milton’s attorneys. McGoldrick also testified that he was uncertain how Judge Gray knew anything about his notes for the 23/23 Deal at the pretrial conference where she mentioned it.

Second, McGoldrick testified that on August 2, 2007, with Milton present, he communicated the 25/20 Deal at least to Reynolds, Milton’s counsel in the drive-by-shooting case. McGoldrick’s file notes for each case substantiate the existence and communication of the 25/20 Deal. That offer remained pending before the preliminary hearing on October 30, 2007. And McGoldrick also testified that he made Milton a better offer in the courtroom immediately before the preliminary hearing began: the 20/20 Deal. McGoldrick did not write a case-file note about having offered the 20/20 Deal.

Third, McGoldrick testified that on August 17, 2007, he told Reynolds, without Milton present, that if Milton succeeded in getting the drive-by-shooting case dismissed, McGoldrick would “probably” pursue the life-without-parole sentence in the drug-trafficking case.11 R. vol. 2 at 137. This effectively meant McGoldrick “probably” wouldn’t make any plea offer that reduced Milton’s pending drug-trafficking charge — the only way Milton could escape Oklahoma’s mandatory life-without-parole sentence applying to that charge. In other words, the 25/20 Deal — the sole offer *1260pending on August 17, 2007 — -was a package deal, and McGoldrick would continue to insist on guilty pleas in both cases.12 McGoldrick testified that he never discussed this approach to prosecuting the cases with Benedict, Milton’s counsel in the drug-trafficking case.

*2. Altshuler’s Testimony*

At the evidentiary hearing, the court also heard from Ashley Altshuler, the prosecutor who took over the drug-trafficking and drive-by-shooting cases after McGoldrick left the district attorney’s office. Most importantly, Altshuler explained how Judge Gray had heard of a 23-year deal: “I believe we had a conversation and I just had the files in front of me and I believe she [Judge Gray] — there may have been a discussion of what the offer was before the prelim.” R. vol. 2 at 215-16. Simply put, Judge Gray knew about a 23-year deal because Altshuler had conversed with Judge Gray while undoubtedly referencing what turned out to be McGoldrick’s written musings about possibly offering the 23/23 Deal — as stated, a possible offer in fact never made.

Understandably, after reading McGol-drick’s notes, Altshuler thought that McGoldrick had offered Milton the 23/23 Deal. But Altshuler already knew that McGoldrick had dated his notes about the 23/23 Deal December 18, 2007, nearly two months after the preliminary hearing. Accordingly, Altshuler told Judge Gray that the pre-preliminary hearing offer had been “25 on possession with intent with all other counts to run concurrent and then also to run concurrent with the 20 in [the drive-by-shooting case]. It was before prelim.” R. vol. 2 at 216.

Amid the multiple plea offers and dates, Judge Gray made an honest mistake. Contrary to Judge Gray’s misunderstanding, McGoldrick had not even contemplated offering the 23/23 Deal Judge Gray had heard about in her conversation with Altshuler until *after*the preliminary hearing, not before it. The 25/20 Deal was the sole offer pending before the preliminary hearing, just as Altshuler had told Judge Gray based on McGoldrick’s notes. A relative newcomer to the case, Altshuler had no way to know about McGoldrick’s offering the 20/20 Deal to Milton in the courtroom immediately before the preliminary hearing began — as mentioned, McGoldrick did not write a note in the file about the offer or Milton’s refusal of it. Altshuler also, could not have known from McGol-drick’s notes whether McGoldrick ever offered Milton the 23/23 Deal, whether on December 18, 2007, or after.

*3. Benedict’s Testimony*

Jacob Benedict, the public defender who represented Milton in the drug-trafficking case, also testified at the evidentiary hearing. Benedict’s case notes and testimony revealed two important facts.

First, Benedict’s case notes indicated that McGoldrick had offered the 25/20 Deal sometime before the preliminary-hearing date.13 Benedict also testified that *1261he recalled, even without any notes, that McGoldrick offered the 20/20 Deal in the courtroom before the preliminary hearing began. Benedict also admitted that he may have erred in the portion of his affidavit where he stated that the pending offer before the preliminary-hearing date was the 20/20 Deal. Instead, after viewing McGoldrick’s case files, Benedict conceded that it probably had been the 25/20 Deal. In addition, Benedict still recalled McGol-drick’s having offered the 20/20 Deal in the courtroom before the preliminary hearing began, consistent with his earlier statement in a different portion of his affidavit.

Second, Benedict corroborated McGol-drick’s earlier testimony: McGoldrick had communicated to Reynolds, but not to Benedict, that McGoldrick would continue to pursue the drug-trafficking case as already charged — resulting in a mandatory life-without-parole sentence in the drug-trafficking case — if the court ultimately’ dismissed the drive-by-shooting case.14 Despite McGoldrick’s failure to communicate this prosecution position to both of Milton’s attorneys, Benedict recalled that Reynolds discussed every other detail relevant to Milton’s plea offers at the preliminary hearing, when Milton and both of his attorneys were present:

> Q: [W]as it ever discussed that a plea might be in Mr. Milton’s best interest?

> A: Well, absolutely. And that would have been the October 30th meeting where — which essentially Joe Reynolds was on point talking with Mr. Milton about the fact that what the offer was, which would have been the 20-year offer on the drive-by case, but that he needed to take care of both of them because they weren’t parsing them out or splitting them up for us.

> [On October 30, 2007, at the preliminary hearing,] I remember it vividly that Mr. Reynolds was essentially telling Mr. Milton that he needed to take the offer from the state. And what I remember vividly was Mr. Milton with his head down shaking his head referencing the drive-by case, that he just — that seemed to be what drove him in his decision-making.

> [Court]: So are you telling the Court that Mr. Reynolds was fairly unequivocal in his recommendation that Mr. Milton take the then pending deal in the drive-by case?

> [A]: Yes.

> [Court]: And that was for [ ] what sentence?

> [A]: That was for a 20-year sentence, which he would have had to serve 85 percent of that sentence. And I recall it as a 20 on possession with intent, but notes within the documents here indicate that it was a 25-year sentence on possession with intent, all running together, concurrent, at the same time.

R. vol. 2 at 273-76.15

*4. Milton’s Testimony*

*1262Milton also testified at the evidentiary hearing. Relevant to this appeal, Milton admitted receiving a 20-year plea offer for the drive-by-shooting case on the day of the preliminary hearing, but he testified that he never received *any*plea offer in the drug-trafficking case. Milton also testified that no one ever told him that any plea offer in one of his two pending cases was contingent on his accepting an offer in the other case. Finally, Milton testified that Reynolds never told him that the State would probably continue to pursue its pending drug-trafficking charge (carrying a mandatory sentence of life without parole) if Milton somehow obtained a dismissal in the drive-by-shooting case.

D. Petition Denied

The district court directed Milton’s ha-beas counsel and the State to submit proposed findings of fact and conclusions of law after the evidentiary hearing. Ultimately, the district court denied Milton’s petition for habeas relief. In doing so, the district court first reviewed the question we posed on remand: “whether petitioner received constitutionally ineffective assistance of appellate counsel as a result of counsel’s failure to pursue, during appellate proceedings, a possible claim of ineffective assistance of trial counsel for failure to communicate a 23-year plea offer” before the October 30, 2007 preliminary hearing. R. vol. 1 at 1155. For clarity, we will refer to this particular habeas claim as Milton’s “Original Claim.”

The district court denied Milton’s Original Claim because, as the evidentiary hearing revealed, McGoldrick considered offering Milton the 23/23 Deal, but McGoldrick never did. ' In view of this, the district court concluded that Milton’s ineffective-assistance-of-appellate-counsel claim failed for lack of prejudice.

Although that ordinarily would have ended the matter, the district court further addressed two brand-new habeas claims Milton fashioned from testimony at the evidentiary hearing. First, the district court turned to what we will term Milton’s “New Claim”: Reynolds was ineffective for “blatantly . failing] to communicate the complete terms of the State’s offer.” *Id.*at 1167. More specifically, Milton argued that Reynolds had failed to communicate McGoldrick’s “warning” that McGoldrick would continue to pursue the pending drug-trafficking charge (again, carrying a mandatory sentence of life without parole) if Milton somehow obtained a dismissal in the drive-by-shooting case. Second, the district court-defined what we will term Milton’s “Other New Claim”: After the preliminary hearing but before trial, Michael Arnett, Milton’s new public defender in the drug-trafficking case, “failed to attempt any negotiation on Mr. Milton’s behalf,” “[denying Milton] the opportunity to resolve his exposure, to punishment for terms of years significantly less than” life without parole. *Id.*

At the outset, the district court held as a matter of law that Milton had failed to exhaust his new claims in the state court. The district court noted that this procedural basis alone was sufficient to dismiss Milton’s new claims. But the district court also addressed the merits of both new claims, ultimately concluding that each lacked merit. The district court denied Milton’s petition for habeas relief and later declined to grant a COA.

Milton now petitions this court for a COA. We address all of Milton’s claims below, both old and new.

*1263II. DISCUSSION

Before Milton can appeal to this court, we must grant him a COA. 28 U.S.C. § 2258(c)(1)(A). We may grant a COA only if the petitioner makes a “substantial showing of the denial of a constitutional right.” *Id.*§ 2258(c)(2). This requires a “showing that reasonable jurists could debate whether (or, for that matter, agree that) the petition should have been resolved in a different manner or that the issues presented were adequate to deserve encouragement to proceed further.” *Slack v. McDaniel,*529 U.S. 473, 484, 120 S.Ct. 1595, 146 L.Ed.2d 542 (2000) (quotation marks omitted). To obtain a COA after a district court has rejected a petitioner’s constitutional claims on the merits, the “petitioner must demonstrate thát reasonable jurists would find the district court’s assessment of the [petitioner’s] constitutional claims debatable or wrong” to obtain a COA. *Id.*

In requesting a COA, Milton has not reasserted his true Original Claim as such. The evidence defeated his claim that his trial counsel had failed to convey a 23-year offer (because no such offer was ever made). Instead, Milton now tries to stretch the canopy of his Original Claim to cover one of his new claims. Even though Milton has abandoned his true Original Claim, we still find it prudent to address the Original Claim to show that Milton is wrong that his new claims are mere amplifications of his Original Claim.

A. The Original Claim

We do not grant Milton a COA with respect to his Original. Claim because Milton does not ask for one. Instead, Milton has wisely abandoned this claim in his current request.

The evidentiary hearing served its purpose. The testimony at the hearing made sense of the conflicting evidence noted in *Milton.*The hearing established, and Milton does not contest, that McGoldrick never communicated the 23/23 Deal to either Reynolds or Benedict because the 23/23 Deal existed only in Benedict’s mind and notes. Obviously, trial counsel could not be ineffective for failing to convey to Milton an offer that the prosecutor never made. In turn, Milton suffered no *Strickland*prejudice for his appellate counsel’s failure to raise what turned out to be a losing issue. Our de novo review of Milton’s original ineffective-assistance-of-appellate-counsel claim, which began with *Milton,*is now complete.

B. The New Claims

Despite fulfilling the goal of our remand, we must address what the district court termed Milton’s “new claims” to the extent Milton pursues them in his current request for a COA.16

*1. Amplification or Alteration?*

Milton argues that his request for a COA does not abandon his Original Claim but includes evidence that merely “clarifies] or amplifies] the claim he made in his original petition for relief.”17 Pet’r’s *1264Request at 30. Milton essentially attempts to recast his Original Claim in broad language that would encompass both his Original Claim and New Claim. Instead of referencing the narrow language of his habeas petition, for example, which explicitly references Reynolds’s failure to communicate *a 23m/ear deal,*Milton argues in his request that “[h]is theory remains unchanged: because of information withheld by his lawyer, Milton forwent a favorable plea offer. That’s what he alleged in his original petition and that’s what he alleges here.” *Id.*at 31. We reject Milton’s attempt to cast his habeas petition in a more favorable light.

Although Milton cites authority one would normally cite to amend a habeas petition, Milton simultaneously argues that his claim remains unchanged (i.e., unamended). *Id.*at 29-30 (citing Fed. R.Civ.P. 15(c)(2); *Mayle v. Felix,*545 U.S. 644, 650, 125 S.Ct. 2562, 162 L.Ed.2d 582 (2005)). He argues that he has always claimed that “one of his trial lawyers failed to inform him of a plea offer made by the prosecutor before the October 30 preliminary hearing.” *Id.*at 30. We disagree that that is what he has always claimed, noting that the New Claim has a dramatically different factual predicate: that Reynolds failed to communicate McGol-drick’s “warning” to continue prosecuting the pending drug-trafficking charge if Milton somehow obtained a dismissal in the drive-by-shooting case. Although this claim and the Original Claim both allege ineffective assistance of counsel, they are separate claims. Milton cannot allege an ineffective-assistance claim and then usher in anything fitting under that broad category as the same claim. Counsel can perform ineffectively in myriad ways. *See Hammon v. Ward,*466 F.3d 919, 926 n. 8 (10th Cir.2006) (considering one ineffee-tive-assistance-of-appellate-eounsel claim but refusing to consider another such claim because the petitioner “did not raise [the latter] claim in his § 2254 habeas petition, and we therefore will not consider it on appeal”). Further, we note that Milton’s COA request has abandoned his original argument that his *appellate*counsel was ineffective. Instead, he now argues that Reynolds, his *trial*counsel, was ineffective. We fail to see how a claim based on trial counsel’s ineffectiveness merely amplifies a claim based on appellate counsel’s ineffectiveness. To the extent Milton is asking us to consider his habeas petition as amended, we note that Milton has never sought to amend his habeas petition, even after the evidentiary hearing, and we cannot allow him to do so now.18 Milton’s New Claim is indeed new.

*2. Presentation and Exhaustion*

Generally, Milton. must have presented his New Claim in his written habeas petition for federal courts to consider it. *See*Rules Governing Section 2254 Cases, Rule 2(c), 28 U.S.C. foil. § 2254; *Adams v. Armontrout,*897 F.2d 332, 334 (8th Cir.1990) (“We hold that in order to substantially comply with the Section 2254 Rule 2(c), a petitioner must state specific, particularized facts which entitle him or her to habeas corpus relief for each ground specified. These facts must consist of sufficient detail to enable the court to determine, from the face of the petition alone, whether the petition merits further habeas corpus review.”). Milton must also have exhausted his New Claim in state court for federal courts to consider it on the merits. *Cullen v. Pinholster,*563 U.S. 170, 181, 131 *1265S.Ct. 1388, 179 L.Ed.2d 557 (2011) (“Sections 2254(b) and (c) provide that a federal court may not grant [a habeas] application!] unless, with certain exceptions, the applicant has exhausted state remedies.”). Milton’s New Claim meets neither requirement. Milton’s New Claim appears nowhere in his habeas petition and he never presented the New Claim to state courts for review.

Ordinarily in this situation, the habeas section of the Antiterrorism and Effective Death Penalty Act of 1996 (AEDPA), 28 U.S.C. § 2254, dictates that we decline Milton’s request for a COA on his New Claim for failure to exhaust but leave open the possibility that Milton might be able to return to the Oklahoma state courts to try to present his New Claim. AEDPA’s structure and policy favors states having the first opportunity to resolve claims their prisoners make. *See O’Sullivan v. Boerckel,*526 U.S. 838, 845, 119 S.Ct. 1728, 144 L.Ed.2d 1 (1999) (“[T]he exhaustion doctrine is designed to give the state courts a full and fair opportunity to resolve federal constitutional claims before those claims are presented to the federal courts____”). But Milton’s case is procedurally unusual for two reasons, both of which justify treating his New Claim differently.

First, despite the New Claim not appearing in Milton’s habeas petition, the district court still chose to reject the New Claim on its merits. The district court did not reject Milton’s New Claim based solely on exhaustion or the claim’s failure to appear on the face of the petition. Second, Milton bases his New Claim on evidence newly revealed at the evidentiary hearing, although outside our narrow remand. With this procedural background, we choose to address the merits of the unexhausted New Claim in determining whether to grant Milton’s request for a COA. In doing so, we stress that new claims arising from this unusual procedural setting are not excused from Rule 2(c)’s petition requirements or the exhaustion requirement.

Ordinarily, to present his new claims on the merits, Milton would have to amend his habeas petition to add his new claims, 28 U.S.C. § 2242, or file a second or successive habeas application in accordance with § 2244, *see Carter v. Bigelow,*787 F.3d 1269, 1277-81 (10th Cir.2015) (concluding that a habeas petitioner adding new claims rather than adding evidence in support of the “precise” claims in his habe-as petition must follow the procedures in § 2244). But sending his New Claim back to the district court after the district court already addressed the New Claim on the merits would only unnecessarily belabor these proceedings.

Similarly, we address Milton’s New Claim despite its being unexhausted because § 2254(b)(2) allows the district court to do so if the New Claim lacks merit. “An application for a writ of habeas corpus may be denied on the merits, notwithstanding the failure of the applicant to exhaust the remedies available in the courts of the State.” 28 U.S.C. § 2254(b)(2); *see Moore v. Schoeman,*288 F.3d 1231, 1235 (10th Cir.2002) (“[Under § 2254(b)(2),] a district court faced with a habeas petition containing unexhausted claims may either (1) dismiss the entire petition without prejudice in order to permit exhaustion of state remedies, or (2) deny the entire petition on the merits.”). In the interest of judicial economy, our court has often considered habeas claims on the merits despite a petitioner’s failure to exhaust. *See Allen v. Mullin,*368 F.3d 1220, 1235 (10th Cir.2004) (reviewing de novo an unexhausted claim and citing § 2254(b)(2)); *Romero v. Furlong,*215 F.3d 1107, 1111 (10th Cir.2000) (“Before addressing Appellant’s ineffective assistance arguments, we note that this case presents a number of complex issues con*1266cerning the applicability of Colorado’s procedural bar to these claims. We need not and do not address these issues, however, because the case may be more easily and succinctly affirmed on the merits.”).

We also note that we may address Milton’s New Claim because, “as the Supreme Court has pointed out, the doctrine[ ] of exhaustion ... raise[s] only federal-state comity concerns and [is] not a jurisdiction[al] limitation of the power of the court.” *Cain v. Redman,*947 F.2d 817, 820 (6th Cir.1991) (pre-AEDPA) (citing *Granberry v. Greer,*481 U.S. 129, 131-36, 107 S.Ct. 1671, 95 L.Ed.2d 119 (1987)); *Strickland v. Thaler,*701 F.3d 171, 174 (5th Cir.2012) (post-AEDPA) (“While a district court should dismiss an entire federal habeas application if the petitioner’s state remedies have not been exhausted as to all claims raised in the federal petition, because exhaustion is based on comity rather than jurisdiction, there is no absolute bar to federal consideration of unexhausted habeas applications.” (quotation marks and citation omitted)).

*3. Substantive Analysis*

We note once more that because the district court denied Milton’s New Claim on the merits, we should only grant a COA for the New Claim if “reasonable jurists would find the district court’s assessment of the [petitioner’s] constitutional claims debatable or wrong.” *Slack,*529 U.S. at 484, 120 S.Ct. 1595.

To succeed on the merits of his New Claim under *Strickland,*Milton must show that: (1) appellate counsel “unreasonably failed to discover [a] nonfrivolous issue[] and to file a merits brief raising [it]”; and (2) prejudice. *Smith v. Robbins,*528 U.S. 259, 285, 120 S.Ct. 746, 145 L.Ed.2d 756 (2000); *see Strickland,*466 U.S. at 694, 104 S.Ct. 2052. In the context of a claim of appellate-counsel ineffectiveness, a defendant can prove prejudice by showing “a reasonable probability that, but for his counsel’s unreasonable failure to” raise the nonfrivolous issue, “he would have prevailed on his appeal.” *Robbins,*528 U.S. at 285, 120 S.Ct. 746. Because we do not believe reasonable jurists would find the district court’s assessment of Milton’s New Claim debatable or wrong, we deny Milton’s request for a COA.

Supporting his New Claim, Milton argues that the district court misunderstood the value of Milton’s knowing the prosecutor’s planned approach to plea bargaining in the drug-trafficking and drive-by-shooting cases. Specifically, Milton argues that, on the day of the preliminary hearing when the State offered the 20/20 Deal, “he was unaware of a vital fact: *if*the drive-by were indeed dismissed there would be no plea bargaining forthcoming on the drug case. But this Milton didn’t know, precisely *because of*his lawyer’s failure to communicate the full terms of the offer he was then pondering.” Pet’r’s Request at 39 (emphases in original). The district court found that this claim lacked merit on three grounds, but we address only one ground because it resolves Milton’s New Claim.

Initially, we take issue with Milton’s argument because of its miseharacterization of the “threatening warning” McGoldrick communicated to Reynolds. *Id.*at 35. McGoldrick simply noted that he would “probably” refuse to reduce the drug-trafficking charge (leaving intact its mandatory life-without-parole sentence) if the drive-by-shooting case were dismissed. R. vol. 2 at 137. But Milton characterizes this “warning” in more fatalistic, certain terms: *“if*the drive-by were indeed dismissed *there would be no plea bargaining forthcoming*on the drug case.” Pet’r’s Request at 39 (second emphasis added). McGoldrick’s position was not so certain, given McGoldrick’s still mulling a possible deal (the 23/23 Deal) long after the preliminary hearing.

*1267Moreover, the district court noted that even if Reynolds had communicated McGoldrick’s warning, “the evidence presented at the hearing thoroughly undermines any suggestion that petitioner would have gone for” any of the offered plea deals. R. vol. 1 at 1169. The district court further explained its reasoning:

> *Without*the warning, petitioner knew that he could take a 20-year, 85% deal on the drug case or stand trial and subject himself to the virtual certainty of a sentence of life without parole. *With*the warning, petitioner would have known, while he pondered a 20-year, 85% deal in the drug case, that if the drive-by case were to be dismissed, he would still face a virtually certain sentence of life without parole in the drug case.

*Id.*(emphases in original). We agree with the district court’s assessment.19

Milton argues that the district court should have added a third alternative: Without the warning, Milton believed he could “reject the offers and defeat the drive-by at the preliminary hearing, thereby reducing the charges he faced from two to one----” Pet’r’s Request at 38. Under this scenario, Milton argues that he “would [have] be[en] free of the drive-by ease, and he could then negotiate a discrete and singular plea bargain on the drug case.” *Id.*Milton couched this argument in the appropriate legal standard:

> In the absence of complete information, Milton took his chances. He rejected the package plea hoping to drive a wedge between two cases linked by fíat of the prosecutor, believing he could defeat one on the evidence and negotiate a settlement of the other. He lost his gamble. The drive-by survived the preliminary hearing. The question, though, is this: would he have taken that chance with full information *before*the hearing? The answer is probably not. To be faithful to the formal legal standard, it is more accurate to say there is a reasonable probability Milton would have eschewed the gamble and instead accepted the 20/20 plea bargain, if only he had full information.

*Id.*at 39 (emphasis in original). But what Milton fails to argue is why he would reasonably believe that the State would reduce his drug-trafficking charge to one not carrying a mandatory life-without-parole sentence because Milton somehow obtained dismissal in the drive-by-shooting case. That defies common sense. In addition, Milton fails to explain why he would have changed his course had he heard of the “warning” about continuing to prosecute the pending drug-trafficking charge (with its mandatory sentence of life without parole) when he had already rejected the 25/20 Deal or the 20/20 Deal.20

*1268Reynolds told Milton that the existing plea deal was a package offer — he would receive no stand-alone offer in either case. *See*R. vol. 2 at 280 (“Mr. Reynolds seemed to control the conversation. And he just discussed the case, discussed the fact that both cases were contingent upon a plea in each case, and that that was probably in his best interest, even though — despite him, Mr. Milton, maintaining his innocence in the [drive-by-shooting] case.”). To any reasonable jurist, Milton’s poor “gamble” was the cause of his current predicament, not the lack of any additional “warning” from Reynolds. Milton knew, based on his conversation with Reynolds on the day of the preliminary hearing, that any existing offer would expire if Milton proceeded with the imminent preliminary hearing, let alone if Milton continued to seek dismissal of the drive-by-shooting case. Even so, Milton rejected the offer and opted for a preliminary hearing on a pending charge that provided for and ultimately resulted in his life-without-parole sentence.

Even after Reynolds told Milton that any existing deal would expire if he chose to proceed with a preliminary hearing, Milton apparently hoped against all odds that McGoldrick would inexplicably reduce Milton’s pending drug-trafficking charge if Milton succeeded in getting his drive-by-shooting case dismissed. But Milton knew that McGoldrick was not obliged to make *any*offer and was not inclined to make an offer on just one of Milton’s cases.

Because we do not believe reasonable jurists could debate that Milton’s New Claim lacks merit based on Milton’s argument above, we deny Milton’s related request for a COA.

III. CONCLUSION

New evidence discovered at the federal evidentiary hearing has assisted our de novo review of Milton’s ineffective-assistance claims, and we conclude that all of them lack merit. Accordingly, we deny Milton’s request for a COA on all bases presented.

1

. In his initial habeas appeal, we granted Milton’s request for a COA only "to appeal the dismissal of his claim of ineffective assistance based on counsel’s alleged failure to inform him of the plea offer.” R. vol. 1 at 959; *see id.*at 953-59.

2

. In this case, a jury convicted Milton of: trafficking in cocaine base after two or more previous felony convictions (mandatory life without parole); possession of a firearm after two or more previous felony convictions (consecutive life sentence with a possibility of parole); possession of marijuana after two or more previous felony convictions (consecutive ten years);. and possession of drug paraphernalia (consecutive one year). We refer to this case as the "drug-trafficking case.”

3

.Milton was formally charged with using a vehicle to facilitate the intentional discharge of a firearm, but for brevity we refer to this case as the'"drive-by-shooting case.”

4

. Specifically, Judge Gray said, “I cannot remember exactly what we put on the record earlier, but the defendant had the opportunity to plead guilty and receive 23 years [in the drug-trafficking case] prior to preliminary hearing and he turned that down.” R. vol. 2 at 215.

5

. The preliminary-hearing conference, distinct from the preliminary hearing, took place on August 2, 2007. The preliminary hearing took place on October 30, 2007.

6

.Only if the prosecutor reduced Milton’s pending drug-trafficking charge could Milton avoid the mandatory life-without-parole sentence upon conviction. *See*R. vol. 2 at 126 ("Q: ... [W]ould it be fair to conclude that on the 2nd of August you offered Joe Reynolds a package deal on both cases: 25, possession with intent, and 20 on the drive-by? A: It would have been to reduce the trafficking to possession with intent, give him 25 on that, 25 on all the other counts contingent on *1256him taking 20 years to do on the drive-by shooting.... Q: You just have to drop the trafficking to possession with intent? A: Yes, ma’am. Q: Okay. And that automatically takes life without parole off the table? A: Yes, ma’am.”).

7

. At this stage of the proceedings, it was unclear whether the supposed 23-year plea offer related to the drug-trafficking case, the drive-by-shooting case, or both.

8

. We further concluded that, in this case, 28 U.S.C. § 2254(e)(2) would not preclude the district court from holding an evidentiary hearing. By asking for an evidentiary hearing on the ineffective-assistance claim in the state courts, Milton hadn’t "failed to develop the factual basis” of his claim. 28 U.S.C. § 2254(e)(2); *see Williams*v. *Taylor,*529 U.S. 420, 432, 120 S.Ct. 1479, 146 L.Ed.2d 435 (2000) ("Under the *opening clause*of § 2254(e)(2), a failure to develop the factual basis of a claim is not established unless there is lack of diligence, or some greater fault, attributable to the prisoner or the prisoner’s counsel.”); *Stouffer v. Trammell,*738 F.3d 1205, 1219 (10th Cir.2013) ("[The prisoner's] counsel asked the trial court for a hearing____ As the State concedes, he raised the issue in his state application for post-conviction re-lief____This is sufficient to satisfy § 2254(e)'s diligence requirement.").

9

. The attorney who represented Milton in the drive-by-shooting case, Joe Reynolds, died before the evidentiary hearing. He therefore could not testify about his recollection of the events in Milton’s case.

10

. The note in McGoldrick’s file for the drug-trafficking case read: “Rec: 23 to do; amend Count 2 to [possession with intent].” R. vol. 2 at 140-41. His note in his file for the drive-by-shooting case: "rec: 23 to do c/c with [the drug-trafficking case].” *Id.*

11

.Specifically, McGoldrick said:

> I told Reynolds that the offer on both cases would go away if this case, being the drive-by case, got dismissed. I would probably proceed with the recommendation of life without parole if the case got dismissed. Mr. Reynolds said he wanted to talk to the defendant and his family about it.

R. vol. 2 at 137.

12

. McGoldrick insisted on Milton’s serving a substantial sentence. In Oklahoma, the drive-by-shooting charge was an "85 percent crime," one conditioning parole eligibility on service of 85% of the sentence imposed. R. vol. 2 at 67. Thus, had Milton accepted offers for the 25/20 or 20/20 Deal, he likely would have served about 17 years concurrently on both offenses. Accordingly, Milton's prison time might well have been the same whether Milton pleaded to the 25/20 Deal or the 20/20 Deal. He would have been eligible for parole in the drug-trafficking case long before he was eligible for parole in the drive-by-shooting case.

13

. Benedict had written a note in his file for the drug-trafficking case saying: "reduce Count 2 to 25 and possession with intent.” R. vol. 2 at 245. This note was located directly below a notation memorializing a 20-year offer in the drive-by-shooting case and above *1261a note indicating the "offer is open until prelim.” R. vol. 1 at 1037. Benedict testified at the evidentiary hearing that, based on these notes, the 25/20 Deal had been conveyed to him.

14

. Benedict also corroborated McGoldrick’s testimony that McGoldrick never offered the 23/23 Deal.

15

. Benedict recounted his vivid recollection of the meeting between him, Milton, and Reynolds later in his testimony, perhaps more succinctly:

> Mr. Reynolds drove it. I think Mr. Milton had a lot more respect for Mr. Reynolds, just because he’s a private attorney, and seemed to listen to him. Mr. Reynolds seemed to control the conversation. And he just discussed the case, discussed the fact that both cases were contingent upon a plea in each case, and that that was probably in his best interest, even though — de*1262spite him, Mr. Milton, maintaining his innocence in the [drive-by-shooting] case.

> R. vol. 2 at 280.

16

. We note that the district court concluded that Milton had actually crafted *two*new claims from evidence at the hearing. We do not address the Other New Claim, however, because Milton has abandoned this claim in his current request for a COA. In his request, Milton did not even reference the factual predicate for the Other New Claim — that Ar-nett was ineffective for failing to negotiate a plea deal *after*the preliminary hearing. We' note, though, that the Other New Claim is distinct from his Original Claim, which primarily concerned the pre-preliminary-hearing conduct of Milton’s counsel. Although both claims involye counsel’s ineffectiveness, that hardly makes them the same claim.

17

. Milton argues that we must construe his pro se habeas petition liberally and that his original petition reflected what Milton knew at the time. We agree that Milton’s pro se petition should be construed liberally, but "we will not rewrite a petition to include claims that were never presented.” *Parker v. Champion,*148 F.3d 1219, 1222 (10th Cir.1998).

18

. In his request, Milton goes so far as to argue the following: "Now that Milton has [new pieces of evidence], he has *inserted them and their meaning*into the record and *into his petition, as he is authorized by Rule 15(c),*to clarify of amplify what has always been his position....” Pet'r’s Request at 33 (emphasis added).

19

. Milton correctly states that the district court appears to have mistaken the drug-trafficking case for the drive-by-shooting case by referring to the drug-trafficking charge as an *85%*crime. But this mistake does not defeat the district court's sound logic in rejecting Milton's New Claim.

20

. The district court made no explicit finding of fact regarding which deal McGoldrick ultimately offered Milton at the preliminary hearing. Rather, the court noted the conflicting testimony we outlined above and concluded:

> It does not appear that the question of whether the offer in the drug case was a 20-year offer or a 25-year offer is of any moment, because the only deal that would have ever been made would have been a package deal including a 20-year sentence in the drive-by case, which would have been an 85% sentence. Thus, the difference being considered for parole in the drug case, after serving one third of a 20-year sentence or one third of a 25-year sentence is of no consequence because petitioner would, in any event, have been required to serve 85% of a 20-year sentence in the drive-by case.

R. vol. 1 at 1161 n. 2. Milton abandons his position that he never heard about the 25/20 *1268Deal or the 20/20 Deal in his request for a COA.