Petitioner-Appellant Michael Williams appeals from the district court’s denial of his habeas corpus petition brought pursuant to 28 U.S.C. § 2254. The only issue before us is whether, having determined that Mr. Williams received ineffective assistance of counsel in rejecting a plea offer, the Oklahoma Court of Criminal Appeals (“OCCA”) fashioned a constitutionally permissible remedy. Our jurisdiction arises under 28 U.S.C. § 1291, and we reverse and remand. On remand, the district court should impose a remedy that comes as close as possible to remedying the constitutional violation, and is not limited by state law.
Background
Prior to trial for first-degree murder, an assistant district attorney offered Mr. Williams a ten-year sentence in exchange for a guilty plea to second-degree murder. Mr. Williams wanted to accept the offer, but his attorney, believing that Mr. Williams was innocent, threatened to withdraw from the case if the offer was accepted. The case proceeded to trial, the jury returned a guilty verdict, and Mr. Williams was sentenced to life imprisonment without the possibility of parole.
On direct appeal, the OCCA remanded the case back to the trial court for an evidentiary hearing on whether Mr. Williams’s trial counsel rendered ineffective assistance during the plea process. After that hearing, the trial court found that trial counsel had rendered deficient performance but also found that Mr. Williams suffered no prejudice. On review, the OCCA held that Mr. Williams’s trial counsel rendered deficient performance and that Mr. Williams was prejudiced thereby because he lost the opportunity to pursue the plea offer with trial counsel. As a remedy, the OCCA modified Mr. Williams’s sentence to life imprisonment with the possibility of parole, which is the lowest punishment for first-degree murder. See Okla. Stat. tit. 21, § 701.9; see also Okla. Stat. tit. 22, § 1066.
Mr. Williams unsuccessfully sought habeas relief in federal district court, contending that the remedy for the ineffective assistance of counsel was inadequate. Without acknowledging the federal principle that the remedy must be tailored to the constitutional violation, the federal district court simply held that the modified sentence fell within the statutory sentencing range for first-degree murder in Oklahoma, and thus the modified sentence was inherently constitutional. Williams v. Jones, No. CIV-03-201-RAW, 2006 WL 2662795, at *12 (10th Cir. Sept. 14, 2006). It relied upon cases (inapposite) involving Eighth Amendment challenges to lengthy sentences within statutory limits. Id. (citing United States v. O’Driscoll, 761 F.2d 589, 599 (10th Cir.1985); Gaines v. Hess, 662 F.2d 1364, 1370 (10th Cir.1981)).
Discussion
We must decide only whether the remedy imposed for the Sixth Amendment violation identified by the OCCA is constitutionally adequate. We granted a COA only on the remedy issue, and a COA is a jurisdictional prerequisite to a decision on the merits of an appeal. 28 U.S.C. § 2253(c)(1); Miller-El v. Cockrell, 537 U.S. 322, 335-36, 123 S.Ct. 1029, 154 L.Ed.2d 931 (2003). The State does not contest the OCCA’s finding of ineffective assistance of counsel in this context. But before resolving the remedy issue, we must consider whether Mr. Williams exhausted his claim.
*1069A. Exhaustion
Notwithstanding the State’s position throughout these proceedings that available state remedies have been exhausted, we raised the issue of exhaustion sua sponte and received supplemental briefs. Of course, a habeas petition maybe denied despite a failure to exhaust. 28 U.S.C. § 2254(b)(2). But it may not be granted unless exhaustion has occurred (or an exception to exhaustion applies). Id. § 2254(b)(1)(A). Although a State may waive exhaustion, such a waiver must be express and through counsel. Id. § 2254(b)(3).
We need not address whether the State has waived exhaustion or whether exhaustion would be futile, because our review of the record persuades us that Mr. Williams did exhaust by requesting a proper remedy from the OCCA when presenting his ineffective assistance of counsel claim. He relied upon federal caselaw in arguing that specific performance of a plea agreement would be a constitutionally permissible remedy and that his conviction should be reversed, the plea reinstated, or the sentence modified. I R. Doc. 1, Ex. 3 at 7-8. He sought a sentence of ten years.
This theme continued in his federal habeas petition, where he sought reinstatement of the ten-year plea or a new trial based upon ineffective assistance of counsel. I R. Doc. 1, Statement of Facts in Support of Habeas Corpus at 81; see also I R. Doc. 1, Ex. 1 at 3; I R. Doc. 1, Ex. 3 at 7-8. Both in the district court and in its response brief on appeal, the State indicated that Mr. Williams had exhausted his state court remedies as to the grounds
raised and argued the merits of the remedy.2 I R. Doc. 17 at 2, ¶ 5; Aplee. Br. at 4, 13-25. Although the magistrate judge remarked in a footnote that Mr. Williams did not argue that the OCCA’s sentence modification denied him his constitutional rights and that such a claim is unexhausted, I R. Doc. 21 at 18 n.2, Mr. Williams was far more specific: he argued that the remedy for ineffective assistance of counsel required a lesser sentence of ten years or a new trial. Were there any doubt, he then objected to the magistrate judge’s report and recommendation on the basis “that the remedy employed by the OCCA is inadequate to vindicate the constitutional error.” I R. Doc. 26 at 5 (emphasis omitted). Accordingly, Mr. Williams properly exhausted his claims.
B. Merits
The federal claims that the OCCA adjudicated on the merits are subject to the familiar statutory deferential standards. Habeas relief may be granted only where the state court’s decision “was contrary to, or involved an unreasonable application of, clearly established Federal law, as determined by the Supreme Court of the United States,” 28 U.S.C. § 2254(d)(1), or “was based on an unreasonable determination of the facts in light of the evidence presented in the State court proceeding,” id. § 2254(d)(2). State court findings of fact are presumed correct unless rebutted by the petitioner by clear and convincing evidence. See id. § 2254(e)(1). Our review of the district court’s legal analysis is de novo. Douglas v. Workman, 560 F.3d 1156, 1170 (10th Cir.2009).
*1070At the same time, where the state court applies a different (wrong) legal standard or does not decide the claim, deferential AEDPA standards do not apply and our review is de novo. Id. In this case, the district court applied Strickland v. Washington, 466 U.S. 668, 104 S.Ct. 2052, 80 L.Ed.2d 674 (1984), to Mr. Williams’s ineffective assistance claims insofar as finding deficient performance and prejudice. Thus, the OCCA identified the correct legal standard3 so our review would be for an unreasonable application. See Williams v. Taylor, 529 U.S. 362, 413, 120 S.Ct. 1495, 146 L.Ed.2d 389 (2000) (an unreasonable application is where the state court applies the correct legal principle in an objectively unreasonable manner). However, in deciding the remedy for the ineffective assistance, the court did not discuss (and may not have been able to apply) the principle that the remedy must be tailored to the injury. United States v. Morrison, 449 U.S. 361, 364, 101 S.Ct. 665, 66 L.Ed.2d 564 (1981). Ultimately, the OCCA settled on a remedy that was consistent with state-law sentencing options for first-degree murder and concluded that it was powerless to reinstate the plea offer even with a reversal and new trial.4
We need not decide whether the remedy selected should be accorded deference as an application of federal law or evaluated de novo because even under a deferential standard of review the remedy was objectively unreasonable. In fashioning the appropriate remedy for ineffective assistance of counsel, the remedy “should be tailored to the injury suffered from the constitutional violation and should not unnecessarily infringe on competing interests.” Id. We think it axiomatic that the remedy for a properly presented constitutional violation should not be frustrated by the sentencing options available under state law, but rather should be consistent with federal law. We proceed to consider the nature of the violation, any resulting prejudice, and the other interests involved.
The plea bargaining process is a critical stage of a criminal prosecution. Nunes v. Mueller, 350 F.3d 1045, 1053 (9th Cir.2003); see Iowa v. Tovar, 541 U.S. 77, *107181, 124 S.Ct. 1879, 158 L.Ed.2d 209 (2004) (entry of the guilty plea is a critical stage of the criminal process); Burger v. Kemp, 483 U.S. 776, 803-04, 107 S.Ct. 3114, 97 L.Ed.2d 638 (1987) (pretrial plea negotiations are a critical stage of the criminal process). Accordingly, the Sixth Amendment applies to representation during the plea process. Hill v. Lockhart, 474 U.S. 52, 57, 106 S.Ct. 366, 88 L.Ed.2d 203 (1985); Jiminez v. State, 144 P.3d 903, 905 (Okla.Crim.App.2006) (“Although we have no published case declaring this point of law, the right to effective counsel guaranteed by the Sixth and Fourteenth Amendments and Article 2, § 20 of the Oklahoma Constitution protects a criminal defendant from objectively deficient representation by defense counsel in connection with the plea bargaining process.”).
Mr. Williams established deficient performance and prejudice. See Strickland, 466 U.S. at 687, 104 S.Ct. 2052; United States v. Carter, 130 F.3d 1432, 1442 (10th Cir.1997); Jiminez, 144 P.3d at 907. The deficient performance was counsel’s advice concerning the plea agreement — advising Mr. Williams he would be committing perjury by accepting the plea offer and insisting that Mr. Williams proceed to trial or find new counsel if he wanted to accept it. As the OCCA no doubt recognized, the prejudice Mr. Williams identified was that, had he been adequately counseled, there is a reasonable probability that he would have accepted the plea offer and limited his exposure to ten years. See Julian v. Bartley, 495 F.3d 487, 498-99 (7th Cir.2007); Satterlee v. Wolfenbarger, 453 F.3d 362, 370 n. 7 (6th Cir.2006); Nunes, 350 F.3d at 1054-55; Wanatee v. Ault, 259 F.3d 700, 703-04 (8th Cir.2001); see also Carter, 130 F.3d at 1442; Jiminez, 144 P.3d at 907. The fact that Mr. Williams subsequently received a fair trial (with a much greater sentence) simply does not vitiate the prejudice from the constitutional violation. See Wanatee, 259 F.3d at 703 (citing Engelen v. United States, 68 F.3d 238, 241 (8th Cir.1995) (collecting cases)); Jiminez, 144 P.3d at 907 (noting defendant’s interest in avoiding trial altogether (citing State v. Garrison, 40 S.W.3d 426, 431 (Tenn.2000))).
The State reminds us that plea offers are discretionary and the assistant district attorney was not required to extend one or keep an offer open. This would be a very different case had the assistant district attorney declined to extend an offer or revoked it prior to trial. See Mabry v. Johnson, 467 U.S. 504, 507-08, 104 S.Ct. 2543, 81 L.Ed.2d 437 (1984), abrogated on other grounds by Puckett v. United States, — U.S. -, 129 S.Ct. 1423, 173 L.Ed.2d 266 (2009); Weatherford v. Bursey, 429 U.S. 545, 561, 97 S.Ct. 837, 51 L.Ed.2d 30 (1977). However, the OCCA found that the ineffective assistance occurred when the plea offer was available. The evidence credited by the OCCA suggests a reasonable probability that the plea offer would have been accepted but for defense counsel’s ineffective assistance. See Satterlee, 453 F.3d at 370 n. 7; Magana v. Hofbauer, 263 F.3d 542, 551 (6th Cir.2001); Jiminez, 144 P.3d at 907. Accordingly, we are not dealing with the government’s discretion to make or withdraw a plea offer. Rather, we are dealing with an offer that was rejected because of defense counsel’s ineffective assistance, with disastrous results for Mr. Williams. In the end, this ineffective assistance and the resulting prejudice is attributable to the State. See Kimmelman v. Morrison, 477 U.S. 365, 379, 106 S.Ct. 2574, 91 L.Ed.2d 305 (1986); Cuyler v. Sullivan, 446 U.S. 335, 343-45, 100 S.Ct. 1708, 64 L.Ed.2d 333 (1980).
The result in this case is unchanged by the fact that the Supreme
*1072Court has commented, in the context of a Sixth Amendment choice of counsel case, United States v. Gonzalez-Lopez, 548 U.S. 140, 147, 126 S.Ct. 2557, 165 L.Ed.2d 409 (2006), that effective assistance serves the purpose of protecting the right to a fair trial. Gonzalez-Lopez recognizes that counsel can be ineffective where “his mistakes have harmed the defense.” Id. Surely, the plea process is part of the defense. See Hill, 474 U.S. at 57, 106 S.Ct. 366. The Court has rejected the idea that “the guarantee of effective assistance of counsel belongs solely to the innocent or that it attaches only to matters affecting the determination of actual guilt.” Kimmelman, 477 U.S. at 380, 106 S.Ct. 2574 (ineffective assistance claims may include failure to seek suppression of evidence even though such claims are barred on collateral review). Moreover, effective assistance is guaranteed for the whole plea process, not just in connection with accepting (but not rejecting) a plea agreement.
Much of the State’s argument on appeal is that what remedy is afforded by the OCCA is solely a matter of State law and no due process violation occurs when the OCCA exercises that power. See Okla. Stat. tit. 22, § 1066 (“The appellate court may reverse, affirm or modify the judgment or sentence.... ”); Clemons v. Mississippi, 494 U.S. 738, 745, 110 S.Ct. 1441, 108 L.Ed.2d 725 (1990); Carbray v. Champion, 905 F.2d 314, 317-18 (10th Cir.1990). The short answer to that is that any correction for a federal constitutional violation must be consistent with federal law; Mr. Williams is not seeking habeas relief for errors of State law, but rather for a Sixth Amendment violation. Moreover, Clemons and Carbray stand for the now unremarkable proposition that a state scheme allowing an appellate court to modify a jury sentence does not constitute a federal constitutional violation; it does not deprive a defendant of a liberty interest in violation of due process. Clemons, 494 U.S. at 745-46, 110 S.Ct. 1441; Carbray, 905 F.2d at 317-19.
The State acknowledges that there are numerous circuit, district, and state court decisions employing various remedies in this context.5 Aplee. Br. at 19; see also Aplee. Br. at 24. We decline to adopt an approach based upon State v. Greuber, 165 P.3d 1185 (Utah 2007), which would hold that a subsequent fair trial vitiates any Sixth Amendment violation. We note this approach is inconsistent with our case law, Carter, 130 F.3d at 1442, and represents an approach rejected by the OCCA not only on federal, but also State, constitutional grounds, Jiminez, 144 P.3d at 907.
The State certainly has an efficiency interest in upholding the modified sentence resulting from a fair trial and partially successful appeal. The State will have incurred the costs of prosecution, and Mr. Williams has defended and tested the State’s case; yet he now will be able to obtain the benefits of the plea offer. Yet the OCCA recognized the obvious merit of reinstating the plea offer were it possible — it would address the prejudice Mr. Williams suffered. See Satterlee, 453 F.3d *1073at 370 n. 7; United States v. Blaylock, 20 F.3d 1458, 1468 (9th Cir.1994). In the end, no remedy may restore completely the parties’ original positions. Still, the OCCA was required to adopt the one that comes closest, without being constrained by state law. See Morrison, 449 U.S. at 365, 101 5. Ct. 665 (“Our approach has thus been to identify and then neutralize the taint by tailoring relief appropriate in the circumstances to assure the defendant the effective assistance of counsel and a fair trial.”). We also note that such an approach is consistent with Oklahoma case law suggesting that the balance should be struck in favor of providing an effective remedy where a defendant has been deprived of a plea agreement due to ineffective assistance. Jiminez, 144 P.3d at 907.
Recognizing the discretion to resolve this issue “as law and justice require,” 28 U.S.C. § 2243, we will remand the case with instructions to the district court to entertain briefing and impose a remedy that comes as close as possible to remedying the constitutional violation, and is not limited by state law. The district court has the power to grant the writ conditionally to allow the State to comply. See Nunes, 350 F.3d at 1056-57.
We have carefully considered Judge Gorsuch’s dissent. There is some common ground — the panel is unanimous that (1) Mr. Williams’s right to counsel attached at the time of plea negotiations, (2) he had a right to effective representation during those negotiations, (3) his counsel rendered deficient performance, and (4) the OCCA’s remedy is insufficient for the federal constitutional violation it found.6 We reject the conclusion expressed in the dissent that Mr. Williams cannot demonstrate prejudice because he received a fair trial subsequent to plea negotiations and was not entitled to a plea offer.
According to the dissent, no remedy exists because no defendant can ever prove prejudice in rejecting a plea given a subsequent fair trial. No federal circuit case so holds. Although the dissent relies upon United States v. Springs, 988 F.2d 746, 749 (7th Cir.1993), the Seventh Circuit follows the same rule we do: a defendant in these circumstances may be entitled to a remedy if he can prove deficient performance and prejudice, i.e., “that but for his lawyer’s advice, he would have taken the plea offer.” Julian, 495 F.3d at 497; see Carter, 130 F.3d at 1442; supra n. 3 (identifying ten circuits). This rule is derived from Strickland and Hill, which provide a similar test when a defendant claims his acceptance of a plea offer was the product of ineffective assistance of counsel. In those circumstances, a defendant must prove deficient performance in connection with the plea process, and but for the deficient performance, he would have gone to trial. Hill, 474 U.S. at 58-59, 106 S.Ct. 366; Strickland, 466 U.S. at 687, 104 S.Ct. 2052.
To the extent that the dissent’s conclusion results from a view that the Sixth Amendment pertains only to trial rights in connection with guilt or innocence, this is a view rejected by the Supreme Court and incompatible with a right to effective assistance of counsel in connection with the entire plea process. Kimmelman, 477 U.S. at 380, 106 S.Ct. 2574; Hill, 474 U.S. at 57, 106 S.Ct. 366. Such an approach also conflicts with the Supreme Court’s rejection of superimposing another requirement on the prejudice inquiry, i.e., the fairness or reliability of the trial pro*1074cess. Williams, 529 U.S. at 394-95, 120 S.Ct. 1495; Short v. Sirmons, 472 F.3d 1177, 1196 (10th Cir.2006). To the extent the dissent’s conclusion results from Mr, Williams’s lack of entitlement to a plea offer, we believe the matter more nuanced — Mr. Williams was entitled to the effective assistance of counsel during plea negotiations, including the decision whether to accept or reject the plea offer. See Nunes, 350 F.3d at 1052-53. He was thereby prejudiced because had he been adequately counseled, there is a reasonable probability that he would have accepted the plea offer and limited his exposure to ten years.
No one contests the rule that plea offers are executory in nature and that, under Mabry and Weatherford, a prosecutor may, consistent with due process, decline to offer or withdraw an offer. But here, the assistant district attorney made an offer that Mr. Williams had a right to accept, as long as it was open, with effective assistance of counsel. See Hill, 474 U.S. at 56, 106 S.Ct. 366 (noting that the voluntariness of any plea depends upon effective assistance of counsel); Strickland, 466 U.S. at 688, 104 S.Ct. 2052 (part of counsel’s duty is to assist the defendant and consult with him on important decisions); Bordenkircher v. Hayes, 434 U.S. 357, 362, 98 S.Ct. 663, 54 L.Ed.2d 604 (1978) (discussing the importance of counsel during plea negotiations). Likewise, this is not a situation where Mr. Williams is claiming ineffective assistance of counsel based upon something to which he had no right, i.e., an objection by counsel based upon an erroneous interpretation of the law. See Lockhart v. Fretwell, 506 U.S. 364, 372-73, 113 S.Ct. 838, 122 L.Ed.2d 180 (1993). Though the dissent may well be right that the options in this case are limited to specific performance or a new trial, in an abundance of caution we would prefer the parties explore any alternatives under a backdrop of the applicable law. Thereafter, the district court may exercise its discretion.
REVERSED and REMANDED.
. There are two pages numbered "8” and both are referenced.
. The State conceded at oral argument that exhaustion would be futile given the OCCA's adherence to state law; the relief sought by Mr. Williams simply goes beyond what state law permitted. See also Aplee. Br. at 8 (acknowledging that the OCCA had no authority to sentence below that which was fixed by statute).
. Hill v. Lockhart, 474 U.S. 52, 56-59, 106 S.Ct. 366, 88 L.Ed.2d 203 (1985), is the most specific case in the plea context. As the OCCA recognized, a defendant may prevail on an ineffective assistance claim in this context by demonstrating deficient performance and prejudice, viz. a defendant is required to show that counsel’s performance fell below an objective level of reasonableness and that, but for counsel’s deficient performance, the defendant would have accepted the plea offer and pled guilty. United States v. Carter, 130 F.3d 1432, 1442 (10th Cir.1997); see also Hill, 474 U.S. at 58-59, 106 S.Ct. 366 (similar test for ineffective assistance of counsel when deficient performance results in acceptance of plea); United Stales v. Mathis, 503 F.3d 150, 152 (D.C.Cir.2007); Julian v. Bartley, 495 F.3d 487, 497-500 (7th Cir.2007); Satterlee v. Wolfenbarger, 453 F.3d 362, 370 n. 7 (6th Cir.2006); United States v. Merritt, 102 Fed. Appx. 303, 307 (4th Cir.2004); Nunes v. Mueller, 350 F.3d 1045, 1054-56 (9th Cir.2003); Wanatee v. Ault, 259 F.3d 700, 703-04 (8th Cir.2001); Smith v. Singletary, 170 F.3d 1051, 1053 (11th Cir.1999); United States v. Gordon, 156 F.3d 376, 380-82 (2d Cir.1998); Teague v. Scott, 60 F.3d 1167, 1170-71 (5th Cir.1995); Jiminez v. State, 144 P.3d 903, 907 (Okla.Crim.App.2006).
. It is worth noting that in similar circumstances (ineffective assistance of counsel based upon failure to communicate a favorable plea offer), the OCCA would later utilize an analytical framework for ineffective assistance similar to what we employ here and modify a sentence to conform to the plea offer. - Jiminez, 144 P.3d at 907. Of course, the State points out that the offense of conviction was the same contained in the plea offer, a fact that differs in this case. The OCCA also observed that, even if the defendant "stands a fair and impartial trial,” he still can be prejudiced by the failure of counsel to convey a plea offer. Id.
. See, e.g., Julian, 495 F.3d at 500 (a court has discretion whether to order a new trial or impose the terms of the original plea offer); Hoffman v. Arave, 455 F.3d 926, 942-43 (9th Cir.2006) (proper remedy is reinstatement of plea offer), vacated in part, 552 U.S. 117, 128 S.Ct. 749, 169 L.Ed.2d 580 (2008); Satterlee, 453 F.3d at 370 n. 7 (defendant should be given an opportunity to accept offer); see also United States v. Gordon, 156 F.3d 376, 381-82 (2d Cir.1998) (grant of new trial was an appropriate remedy); Jiminez, 144 P.3d at 907 (sentence modified to conform to term in plea agreement). Our circuit has considered a claim for specific performance of a plea agreement, but rejected it based on an inadequate showing of deficient performance and prejudice. Carter, 130 F.3d at 1442.
. Of course, the dissent contends that there is no constitutional violation hence any remedy was unnecessary.