Opinion by Judge THOMAS; Partial Concurrence and Partial Dissent by Judge TALLMAN.

In this case, we consider whether a prosecutor’s knowing presentation of false evidence and failure to correct the record violate a criminal defendant’s due process rights. We conclude that such actions violate due process, and we therefore reverse the district court’s denial of the petition for a writ of habeas corpus.

I

This case concerns the 1980 murder of Vinod “Pete” Patel by Blufford Hayes, Jr. Patel was the resident hotel manager of the Rice Motel in Stockton, California. Hayes was staying in Room 15 of the motel with his sister, Barbara Lord. Hayes once resided at the motel himself, but had been evicted when he stopped paying rent. Several days before Patel’s death, Patel had asked the police to arrest Hayes for trespassing because he had broken into his former room. Officers found Hayes in his former room with fresh needle marks on his arm; he admitted to breaking in, but said he intended to pay rent as soon as he could. The police arrested him for tres *975 passing and for being under the influence of a controlled substance.

Hayes returned to the Rice Motel on New Year’s Eve, December 31, 1979, to visit his sister in her room. Hayes testified that, as of New Year’s Eve, he had been awake for three days, had injected heroin and Ritalin, and had consumed a large amount of brandy. On the morning of New Year’s Day, Lord left for work, leaving Hayes alone in the motel room. At trial, Lord testified that her bathroom sink had been leaking for some time. She had told Patel about the leak, but he had not fixed it. Lord testified that she saw Patel as she left for work on the morning of New Year’s Day, and that she may have mentioned the leak to him again.

At around 9:30 a.m., Bearla Mae Wyatt, who lived next door to Lord in Room 16, went to the motel’s office to get some fresh towels. In the office, Wyatt encountered Hayes and Patel. Hayes was telling Patel that there was a problem with the bathroom sink in Room 15 and that he wanted Patel to come and fix it. Patel did not understand Hayes’s explanation and invited Hayes to demonstrate what he meant in Patel’s own living quarters, which adjoined the office. Because Patel was occupied, Wyatt left; when she returned 10 to 15 minutes later, Hayes and Patel were coming out of Patel’s bathroom area. Wyatt heard Patel tell Hayes that he would “be down at the room later on.”

Hayes testified that, after his discussion with Patel at the motel office, Hayes returned to Room 15, went to a store to buy a bottle of wine, returned to the motel room, drank some wine, and went to sleep. According to Hayes,' the next thing he recalled was being awakened by someone slapping him and saying something that he could not understand. He claimed that he struck back and thereafter realized it was Patel. Hayes testified that, as he was getting' off the bed, he noticed that Patel had a knife. Hayes said he struggled with Patel, forced Patel to drop the knife, and then picked the knife up himself.

Hayes testified that he thereafter tried to stop the manager from grabbing a butcher knife that was on top of the dresser, and ended up stabbing Patel on the arm and chest. According to Hayes, Patel backed away into the bathroom and made a loud noise. Patel then walked out and collapsed on the floor. Hayes said he then picked up the butcher knife from the floor and put it in a dresser drawer to put it outside Patel’s reach. He also picked up a bottle of wine and placed it into the same drawer. Hayes righted a chair that had been knocked over and picked up a pouch and vest from the floor and put them on-the bed. He then unwound two wire coat hangers and bound Patel’s hands and feet while Patel was still alive. Hayes explained that he did not want to have to hurt Patel anymore and was afraid of what' Patel might do if he got up.

A short time later, Hayes went to the motel room shared by Andrew “A.J.” James and his girlfriend, Michele Gebert; Hayes had known both James and Gebert for' many years. Hayes told them he wanted James to give him a ride. Hayes testified that he told James that he had had to “down” someone. James said that he did not believe Hayes, and left the room to see for himself. Gebert testified that she commented to Hayes about the possibility of Patel calling the police, and Hayes allegedly replied, that “[Patel] would not say anything to anybody.” Hayes testified that he looked out the door of James and Gebert’s apartment and saw James, not in Hayes’s room, but at the motel office. According to his testimony, Hayes then went to the office, where he saw James taking cartons of cigarettes. Hayes testified that, at James’s request, he also carried two *976 boxes himself. Hayes and James left together in James’s car.

Wyatt testified that, about thirty minutes after she saw Hayes and Patel in the motel office, by which time she had returned to her room, she looked out her window and saw Hayes carrying a box across the motel parking lot to a car. She’ noticed that James was standing at the side of the ear. A few moments later, she looked out the window again and saw James carrying something out of his room. She could not recall what James was carrying, but it “seemed like he was moving out” because there was a lot of movement back and forth.

According to James, when Hayes arrived at James’s room, James woke up, went to the bathroom, and left with Hayes. James testified that the two went to James’s car. There, James noticed that two boxes of cigarettes, each containing thirty cartons, were in the car. The location of the boxes is unclear. At one point, James testified that the boxes of cigarettes were in the trunk. At other times, James testified that the boxes were in the back seat. According to James, Hayes asked James if he knew where to get rid of the cigarettes, but James said he did not. James kept one carton for himself, however.

James testified that Hayes told him in the car that Hayes had “offed” the motel manager. When James expressed his disbelief, Hayes explained that the manager had awakened him and had “swung on him” so Hayes “did the do with him.” James also testified that Hayes further advised James that he “tore” up the office looking for money. James drove Hayes to Hayes’s mother’s house, helped unload the cigarettes, and then drove straight back to the motel, where he noticed that the door of the motel’s office was open. He left in the car with Gebert, and they drove around for several hours discussing what to do. James was afraid to go to the police because he “had cases at the time.” Gebert eventually called the police, and Gebert and James later went to the police station to be interviewed.

When Lord returned to Room 15 that afternoon, she found Patel’s dead body lying on the floor. His hands and feet were bound with coat hangers. Patel had suffered at least twenty-two cutting and stabbing wounds, including eight stab wounds to the front of his chest. Six stab wounds penetrated the chest cavity, any one of which could have been fatal. The wounds to Patel’s left hand and forearm were determined to be “defensive wounds,” which the coroner defined as “wounds incurred by the victim as he is trying to ward off the attacker.”

At the crime scene, the police located a butcher’s knife inside a dresser drawer. Inside the bathroom, the police found “splattered” blood on “quite a few spots.” There were also signs of struggle inside the bathroom, as reflected by a toppled plastic trash can and damage to the door frame of the shower. Outside the bathroom, the only blood observed was a pool under Patel’s body, and stains on some items on the bed. There was no overturned furniture in the room, according to a police officer who viewed the scene. The police also discovered a light blue, long-sleeved shirt and a dark blue vest, both stained with blood. Hayes and Patel had the same blood type, and the blood on the clothing was consistent with this type. The motel’s office and Patel’s adjoining living quarters appeared to have been ransacked. The office cash box, which generally held $40 to $50, was found empty.

Hayes was arrested in Oregon, and tried before a San Joaquin County, California, jury. The prosecution flew James, who had left California, back from Florida for *977 the trial, with the promise that he could return to Florida after testifying. James had a criminal history, having been convicted of petty theft, grand theft;.and receiving stolen property. At the time he testified, he also had pending in California three charges of felony theft with a prior conviction, and a charge of being under the influence of heroin. Before trial, the prosecutor had reached an agreement with James’s attorney to grant transactional immunity for the Patel killing and to dismiss the other pending unrelated felony charges against James. However, - the State wished to keep the promise to dismiss the felony charges away from the trial .judge and jury. Therefore, the prosecutor extracted a promise from James’s attorney that he would not tell James about the deal. The idea was that James would be able to testify that there was no deal in place, without perjuring himself, because James would not personally be informed of the arrangement.

The jury convicted Hayes of first-degree murder (CaLPenal Code § 187), burglary, and robbery, and it found true the two special circumstances of robbery-murder and burglary-murder. Cal.Penal Code § 190.2(a)(17)(A) & (G). On November 25, 1981, the same jury returned a verdict imposing a death sentence.

After he testified, James returned to Florida with an airplane ticket paid for by the prosecution, even though the California felony charges were still pending, and he had not been arraigned. Shortly thereafter, the State dismissed all felony charges against James.

Hayes appealed from the conviction and sentence to the California Supreme Court, which reversed the conviction and sentence for robbery, and the robbery-murder special circumstance, but otherwise affirmed the judgment, including the imposition of the death penalty. People v. Hayes, 52 Cal.3d 577 , 276 Cal.Rptr. 874 , 802 P.2d 376 (1990).

In June 1993, Hayes filed a federal petition for a writ of habeas corpus consisting of 61 claims. The .district court dismissed 38 unexhausted claims, without prejudice, and ordered Hayes to present the claims, to the California Supreme Court. Hayes filed those claims, and five additional claims, in a second petition for writ of habeas corpus in the California Supreme Court. That court denied all relief.

Hayes then filed a first amended petition in federal court on August 28, 1995, asserting 65 claims. The State of California moved to dismiss some of the claims on the ground that they were denied by the California Supreme Court on procedural grounds, thereby barring federal review. The motion was denied. A four-day evi-dentiary hearing was conducted on Hayes’s allegedly unconstitutional absence from the entire penalty phase of the trial, and a separate two-day evidentiary hearing was conducted regarding the alleged ineffective assistance of counsel regarding a plea-bargain offer.

Both parties moved for summary judgment on the merits, and the magistrate judge recommended that the State’s motion for summary judgment be granted as to all claims and that the habeas petition be denied. After de novo review, the district court filed an order specifically addressing some of Hayes’s claims, adopting the magistrate judge’s findings and recommendations in full, and denying the petition. The district court granted Hayes a certificate of appealability for the arguments he makes on appeal. A divided panel of our Court issued an opinion affirming the district court’s grant of summary judgment. A majority of the 1 non-recused, active judges of this Court voted to rehear the appeal en banc.

*978 Hayes filed his 28 U.S.C. § 2254 petition for a writ of habeas corpus before the enactment of the Antiterrorism and Effective Death Penalty Act of 1996 (“AED-PA”). Therefore, our review is governed by pre-AEDPA standards. See, e.g., Lindh v. Murphy, 521 U.S. 320, 326 , 117 S.Ct. 2059 , 138 L.Ed.2d 481 (1997); Karis v. Calderon, 283 F.3d 1117 , 1126 n. 1 (9th Cir.2002).

McKenzie v. McCormick, 27 F.3d 1415, 1418 (9th Cir.1994) (citation and quotation marks omitted).

II

The Supreme Court has long emphasized “the special role played by the American prosecutor in the search for truth in criminal trials.” Strickler v. Greene, 527 U.S. 263, 281 , 119 S.Ct. 1936 , 144 L.Ed.2d 286 (1999). As we observed in Commonwealth of The Northern Mariana Islands v. Mendiola, 976 F.2d 475, 486 (9th Cir.1992) (citations omitted), overruled on other grounds by George v. Camacho, 119 F.3d 1393 (9th Cir.1997) (en banc):

One of the bedrock principles of our democracy, “implicit in any concept of ordered liberty,” is that the State may not use false evidence to obtain a criminal conviction. Napue v. Illinois, 360 U.S. 264, 269 , 79 S.Ct. 1173 , 3 L.Ed.2d 1217 (1959) (internal citation omitted). Deliberate deception of a judge and jury is “inconsistent with the rudimentary demands of justice.” Mooney v. Holohan, 294 U.S. 103, 112 , 55 S.Ct. 340 , 79 L.Ed. 791 (1935). Thus, “a conviction obtained through use of false evidence, known to be such by representatives of the State, must fall under the Fourteenth Amendment.” Napue, 360 U.S. at 269 , 79 S.Ct. 1173 (citations omitted). “Indeed, if it is established that the government knowingly permitted the introduction of false testimony reversal is ‘virtually automatic.’ ” United States v. Wallach, 935 F.2d 445, 456 (2d Cir.1991) (quoting United States v. Stofsky, 527 F.2d 237, 243 (2d Cir.1975)).

In addition, the state violates a criminal defendant’s right to due process of law when, although not soliciting false evidence, it allows false evidence to go uncorrected when it appears. See Alcorta v. Texas, 355 U.S. 28 , 78 S.Ct. 103 , 2 L.Ed.2d 9 (1957); Pyle v. Kansas, 317 U.S. 213 , 63 S.Ct. 177 , 87 L.Ed. 214 (1942).

A

In this case, the State knowingly presented false evidence to the jury and made false representations to the trial judge as to whether the State had agreed not to prosecute James on his pending felony charges. James’s attorney testified in federal court that there had been a deal between himself and then-Deputy District Attorney Terrence Van Oss. The district court specifically found:

*979 The district judge noted that, in a file entry dated February 7, 1980, James’s attorney wrote:

(Material in brackets supplied by district court.)

The district court noted that “[subsequent entries state that ‘the case will be disposed of after Hayes trial’ and ‘case to be dismissed on 12/15/81.’ ” The district court also found that, “[i]n an evidentiary hearing in another case, Van Oss testified that he had no basis for disputing these notes, conceding at one point that he ‘must have told him.’ ”

In his Report and Recommendation, the magistrate judge stated:

This finding is amply supported by the record. Although felony charges against James were pending, the State assisted him in moving to San Diego. James later moved to Florida. The government paid for his airplane transportation from Florida to California to testify in the Hayes trial. James freely traveled to California, apparently without fear that he would be placed in custody on the pending felony charges. The notes from James’s attorney indicate that a court appearance on his charges was scheduled for October 20, 1981, but was continued until November 17, 1981. James testified at the Hayes trial on October 29, 1981. The jury returned a guilt-phase verdict on November 16, 1981.. The next day, the chief prosecutor in the Hayes trial,,Terrence Van Oss, appeared at the continued arraignment scheduled for James. The transcript of the hearing reflects there was a discussion off the record with the judge, after which the arraignment was continued until December 15, 1981. James’s counsel’s notes on November 17, 1981, said that “case to be dismissed] on 12/15/81. We need not appear.” The jury returned its verdict of punishment by death on November 25, 1981. On December 15, 1981, the charges against James were dismissed, and the State paid for James’s safe return to Florida by air.

In addition to the fact of the deal, the record also supports the finding that a key part of the agreement was to keep James in the dark, so that he could testify that there was no deal without perjuring himself. James’s attorney wrote in,his notes of the conversation about the deal:

(Emphasis in original.)

After making this -arrangement, the State misled the trial judge. In preliminary proceedings, defense counsel inquired “whether any negotiated settlement has been made in return for his [James’s] -testimony.” To that, the prosecutor responded:

*980 Upon farther inquiry by the trial judge about “whether there has been any negotiations,” the prosecutor replied:

When James testified, the prosecutor elicited the following testimony:

After defense counsel probed in cross-examination the lack of activity in prosecuting James, with James responding that the charges were still pending, the prosecutor elicited the following testimony from James on redirect:

In closing, the prosecutor emphasized the truthfulness of the State’s witnesses, stating:

Thus, the record is clear that: (1) before the Hayes trial, the State had made a deal with James’s attorney for the dismissal of pending felony charges after his testimony; (2) the State specifically represented to the trial judge that there was no such deal; (3) the State elicited sworn testimony from James at trial that there was no such deal, both on direct and re-direct examination; and (4) the State failed to correct the record at trial to reflect the truth.

The State’s actions violated Hayes’s constitutional rights first under Napue , by presenting false evidence to the jury and, second, under Alcorta and Pyle , by failing to correct the record following the presentation of false evidence.

B

The State contends that there was no Napue violation because James did not commit perjury. According to the State, Napue renders unconstitutional only acts of perjury. Therefore, the State reasons, because James was ignorant of the deal, he did not commit perjury and the State did not run afoul of Napue . In short, the State contends that it is constitutionally permissible for it knowingly to present false evidence to a jury in order to obtain a conviction, as long as the witness used to *981 transmit the false information is kept unaware of the truth.

The State is wrong. Napue , by its terms, addresses the presentation of false evidence, not just subornation of perjury. As Chief Justice Warren wrote:

360 U.S. at 269 , 79 S.Ct. 1173 (citations omitted). In describing the rule, the Court itself discussed the use of “false evidence, including false testimony....” Id. There is nothing in Napue , its predecessors, or its progeny, to suggest that the Constitution protects defendants only against the knowing use of perjured testimony. Due process protects defendants against the knowing use of any false evidence by the State, whether it be by document, testimony, or any other form of admissible evidence. See Phillips v. Woodford, 267 F.3d 966, 984-85 (9th Cir.2001) (“It is well settled that the presentation of false evidence violates due process.”) (citing Napue, 360 U.S. at 269 , 79 S.Ct. 1173 ).

Further, contrary to the State’s theory, that the witness was tricked into lying on the witness stand by the State does not, in any fashion, insulate the State from conforming its conduct to the requirements of due process. As our court noted in Northern Mariana Islands v. Bowie, 243 F.3d 1109, 1114 (9th Cir.2001): “Few things are more repugnant to the constitutional expectations of our criminal system than covert perjury .... ” It is reprehensible for the State to seek refuge in the claim that a witness did not commit perjury, when the witness unknowingly presents false testimony at the behest of the State. “This saves [the witness] from perjury, but it does not make his testimony truthful.” Willhoite v. Vasquez, 921 F.2d 247, 251 (9th Cir.1990) (Trott, J., concurring). The fact that the witness is not complicit in the falsehood is what gives the false testimony the ring of truth, and makes it all the more likely to affect the judgment of the jury. That the witness is unaware of the falsehood of his testimony makes it more dangerous, not less so. 1

There is nothing redemptive about the sovereign’s conspiring to deceive a judge and jury to obtain a tainted conviction. This is, as Judge Trott put it, “a pernicious scheme without any redeeming features.” Id. Napue forbids the knowing presentation of false evidence by the State in a criminal trial, whether through direct presentation or through covert subornation of perjury. 2

Further, the argument that the presentation of false testimony, carefully orchestrated to avoid perjury, does not offend the Constitution flies in the face of Alcorta and Pyle because those cases create an affirmative duty on the part of the prosecution to correct false testimony at trial, even when the testimony is unsolicited. There is no exception under Alcorta and Pyle for solicited false testimony. The State’s knowing presentation of false evidence and failure to correct the record at *982 Hayes’s trial violated the Fourteenth Amendment.

C

The State argues that the constitutional prohibition against the knowing presentation of false evidence, as distinguished from the prohibition against suborning perjury, is a new rule of constitutional procedure that cannot be applied to this case under Teague v. Lane, 489 U.S. 288 , 109 S.Ct. 1060 , 103 L.Ed.2d 334 (1989). Subject to a few exceptions, Teague holds that, “[ujnless they fall within an exception to the general rule, new constitutional rules of criminal procedure will not be applicable to those cases which have become final before the new rules are announced.” Id. at 310 , 109 S.Ct. 1060 .

The threshold question in a Teague analysis is whether the rule that the petitioner seeks to apply is a substantive rule or a procedural rule, because “Teague by its terms applies only to procedural rules.” Bousley v. United States, 523 U.S. 614, 620 , 118 S.Ct. 1604 , 140 L.Ed.2d 828 (1998). If the rule is procedural, the court then conducts a three-step analysis to determine whether Teague bars its application. See O’Dell v. Netherland, 521 U.S. 151, 156-57 , 117 S.Ct. 1969 , 138 L.Ed.2d 351 (1997). First, the reviewing court “must ascertain the date on which the defendant’s conviction and sentence became final for Teague purposes.” Caspari v. Bohlen, 510 U.S. 383, 390 , 114 S.Ct. 948 , 127 L.Ed.2d 236 (1994). Second, the court must survey “the legal landscape as it then existed,” Graham v. Collins, 506 U.S. 461, 468 , 113 S.Ct. 892 , 122 L.Ed.2d 260 (1993), to determine whether existing precedent compelled a finding that the rule at issue “was required by the Constitution.” Lambrix v. Singletary, 520 U.S. 518, 527 , 117 S.Ct. 1517 , 137 L.Ed.2d 771 (1997) (internal quotation marks and citations omitted). If existing precedent already required application of the rules, the Teague bar does not apply. However, if the procedure at issue is considered a new rule for Teague purposes, the court must proceed to the third step and determine whether either of the two announced exceptions applies. Teague, 489 U.S. at 307 . The presumption against retroactivity is overcome only if the new rule prohibits “a certain category of punishment for a class of defendants because of their status or offense,” Penry v. Lynaugh, 492 U.S. 302, 330 , 109 S.Ct. 2934 , 106 L.Ed.2d 256 (1989), abrogated on other grounds by Atkins v. Virginia, 536 U.S. 304 , 122 S.Ct. 2242 , 153 L.Ed.2d 335 (2002), or presents a new “watershed rule[] of criminal procedure” that enhances accuracy and alters our understanding of bedrock procedural elements essential to the fairness of a particular conviction. Teague, 489 U.S. at 311 , 109 S.Ct. 1060 (citations omitted).

Thus, we must first ask whether the prohibition against the knowing presentation of false evidence is substantive or procedural law. For Teague purposes, a new rule is one of “procedure” if it affects the operation of the criminal trial process, and a new rule is one of “substance” if it alters the scope or modifies the applicability of a substantive criminal statute. Bousley, 523 U.S. at 620 , 118 S.Ct. 1604 . The prohibition on the use of false evidence by the State at trial is clearly a procedural rule; it affects the operation of the criminal trial process, but does not affect the scope of a substantive criminal statute.

Because the rule is procedural, we proceed to the three-step analysis to determine whether the rule was “new.” We begin by ascertaining the date on which Hayes’s conviction became final. Caspari, 510 U.S. at 390 , 114 S.Ct. 948 . In 1990, the California Supreme Court upheld Hayes’s conviction in relevant part. Peo *983 ple v. Hayes, 52 Cal.3d 577 , 276 Cal.Rptr. 874 , 802 P.2d 376 (1990). The United States Supreme Court denied Hayes’s petition for a writ of certiorari on November 12, 1991. Hayes v. California, 502 U.S. 958 , 112 S.Ct. 420 , 116 L.Ed.2d 440 (1991). Thus, Hayes’s conviction became final on that date. See Griffith v. Kentucky, 479 U.S. 314 , 321 n. 6, 107 S.Ct. 708 , 93 L.Ed.2d 649 (1987) (“By ‘final,’ we mean a case in which a judgment of conviction has been rendered, the availability of appeal exhausted, and. the time for a petition for certiorari elapsed or a petition for certiora-ri finally denied.”) (citations omitted).

Next, we survey “the legal landscape as it then existed,” Graham, 506 U.S. at 468 , 113 S.Ct. 892 , to determine whether existing precedent compelled a finding that the rule at issue “was required by the Constitution.” Lambrix, 520 U.S. at 527 , 117 S.Ct. 1517 . The suggestion by the State that, as of 1991, the Constitution did not prohibit the government from knowingly presenting false evidence to obtain a criminal conviction is somewhat startling. There is nothing new at all about this constitutional protection. We have already .noted that Napue , decided nearly a half century ago, specifically addressed, “false evidence,” and was not limited to barring the subornation of perjury. Alcor-ta and Pyle , which require the State to correct false facts introduced as evidence at trial, were decided in 1957 and 1942, respectively. Indeed, as we stated in Bowie :

236 F.3d at 1087.

The rule originated with Mooney in 1935, which held that a criminal defendant is denied due process when the “state has contrived a conviction through the pretense of a trial which in truth is but used as a means of depriving a defendant of liberty, through a deliberate deception of court and jury by the presentation of testimony known to be perjured.” 294 U.S. at 112 , 55 S.Ct. 340 . Seven years later, in Pyle , the Supreme Court expanded this rule to; encompass not only “perjured testimony, knowingly used by the State,” but also “the deliberate suppression by those same authorities of evidence favorable to[the criminal defendant].” 317 U.S. at 216, 63 . S.Ct. 177.

Alcorta , decided in 1957, involved a case quite similar to the one at bar. In that case, the Court was confronted with a prosecutor, who, on direct examination, knowingly allowed a witness to create a' false impression. 355 U.S. at 29-30 , 78 S.Ct. 103 . The prosecutor had instructed the witness not to volunteer what the prosecutor thought might be damaging information and then sat mute while the witness committed perjury. Id. at 31 , 78 S.Ct. 103 . In granting Alcorta’s petition for a writ of habeas corpus, the Court held that the false impression given to the jury by' the prosecutor and the State violated Alcorta’s right to due process. Id.

Napue , which we have discussed, was decided two years later. Napue quoted with approval a decision from the New York Court of Appeals involving false testimony from a'witness who had been given substantial consideration for his testimony, in which that court stated: “ ‘A lie is a lie, no matter what its subject, and, if it is in any way relevant to the case, the district attorney has the responsibility and duty to *984 correct what he knows to be false and elicit the truth.’ ” 360 U.S. 264, 269-70 , 79 S.Ct. 1173 , 3 L.Ed.2d 1217 (1959) (quoting People v. Savvides, 1 N.Y.2d 554 , 154 N.Y.S.2d 885 , 136 N.E.2d 853, 854-55 (1956)).

In United States v. Bagley, 473 U.S. 667, 678 , 105 S.Ct. 3375 , 87 L.Ed.2d 481 (1985), the Supreme Court noted the “well-established rule that ‘a conviction obtained by the knowing use of perjured testimony is fundamentally unfair, and must be set aside if there is any reasonable likelihood that the false testimony could have affected the judgment of the jury.’ ” (Citation omitted).

Thus, the rule has been clear for decades: a criminal defendant is denied due process of law when a prosecutor either knowingly presents false evidence or fails to correct the record to reflect the true facts when unsolicited false evidence is introduced at trial. We need not proceed to the remainder of the Teague analysis. There being nothing new about this rule, it does not implicate Teague .

Ill

A

That constitutional error occurred does not end our analysis. Neither Napue nor Alcorta creates a per se rule of reversal. Because the error was not structural, we must assess whether the constitutional violation was material. See United States v. Zuno-Arce, 339 F.3d 886, 889 (9th Cir.2003) (“To prevail on a claim based on Mooney-Napue, the petitioner must show that (1) the testimony (or evidence) was actually false, (2) the prosecution knew or should have known that the testimony was actually false, and (3) ... the false testimony was material.”) (citations omitted).

In assessing materiality under Napue , we determine whether there is “ ‘any reasonable likelihood that the false testimony could have affected the judgment of the jury;’ ” if so, then “the conviction must be set aside.” Belmontes v. Woodford, 350 F.3d 861, 881 (9th Cir.2003) (quoting United States v. Agurs, 427 U.S. 97, 103 , 96 S.Ct. 2392 , 49 L.Ed.2d 342 (1976)). Under this materiality standard, “ ‘[t]he question is not whether the defendant would more likely than not have received a different verdict with the evidence, but whether in its absence he received a fair trial, understood as a trial resulting in a verdict worthy of confidence.’ ” Hall v. Director of Corrections, 343 F.3d 976, 983-84 (9th Cir.2003) (per curiam) (quoting Kyles v. Whitley, 514 U.S. 419, 434 , 115 S.Ct. 1555 , 131 L.Ed.2d 490 (1995)).

Evthough this case comes to us on habeas review, we do not conduct an additional harmless error analysis under Brecht v. Abrahamson, 507 U.S. 619 , 113 S.Ct. 1710 , 123 L.Ed.2d 353 (1993), which asks whether the error “ ‘had substantial and injurious effect or influence in determining the jury’s verdict.’ ” Id. at 623 , 113 S.Ct. 1710 (citation omitted). When the Supreme Court has declared a materiality standard, as it has for this type of constitutional error, there is no need to conduct a separate harmless error analysis. As the Supreme Court explained in Kyles , when considering a similar question about applying the Bagley disclosure requirements, the required finding of materiality necessarily compels the conclusion that the error was not harmless. 514 U.S. at 435 , 115 S.Ct. 1555 .

Application of the Agurs “any reasonable likelihood” standard necessarily forecloses a Brecht harmless error analysis. The Supreme Court noted in Kyles that, in Agurs , the Court had expressly considered and rejected the harmless error standard *985 established in Kotteakos v. United States, 328 U.S. 750, 776 , 66 S.Ct. 1239 , 90 L.Ed. 1557 (1946), which formed the basis for the standard enunciated in Brecht . 'Therefore, the Court reasoned in Kyles , for all errors that derived from the Agurs materiality-standard, there was no need to conduct a separate Brecht analysis. Kyles, 514 U.S. at 436 , 115 S.Ct. 1555 . Thus, for example, because the prejudice analysis in Strickland v. Washington, 466 U.S. 668 , 104 S.Ct. 2052 , 80 L.Ed.2d 674 (1984), derived from the Agurs materiality standard, federal courts do not conduct a separate Brecht analysis in ineffective assistance of counsel claims. Kyles, 514 U.S. at 436 , 115 S.Ct. 1555 ; see also Pirtle v. Morgan, 313 F.3d 1160, 1169 (9th Cir.2002); Avila v. Galaza, 297 F.3d 911 , 918 n. 7 (9th Cir.2002); Jackson v. Calderon, 211 F.3d 1148 , 1154 n. 2 (9th Cir.2000).

Applying the same logic, we concluded in Belmontes that the Agv/rs standard applies to Napue claims. 350 F.3d at 881 . Thus, once we have determined whether the Napue error was material under the Agurs standard, we do not conduct a separate Brecht examination. The materiality analysis is complete in itself; there is no ne,ed for a separate harmless error review.

B

The remaining .question .in this case is whether there is “any reasonable likelihood that the false testimony could have affected the judgment of the jury.” Belmontes, 350 F.3d at 881-82 . The jury convicted Hayes of the charge of first-degree murder under a felony murder theory, finding Hayes “guilty of a violation of Section 187 of the Penal Code of the State of California, to-wit: murder, in the first degree, committed while the defendant was engaged in the commission of ... -a' burglary.” 3 The jury found true the special circumstance that Hayes committed a murder while “engaged in the commission of, or the immediate flight after committing burglary, a felony.” 4

To convict Hayes of felony murder, the jury had to decide whether Hayes murdered Patel “as a result of the commission of’ a burglary. Thus, a pivotal question before the jury was whether Hayes had formed the intent to burglarize the office before killing Patel. The State’s theory was that Hayes had lured Patel into the motel room for the purpose of murdering him so that Hayes could burglarize the motel’s office. Hayes’s theory was that a spontaneous fight occurred when Patel arrived at the- motel room. Hayes contended that James was the one who initiated the office burglary after Hayes had come over to James’s room to get a ride away from the motel after the killing.

Thus, by any measure, James was a key witness. Indeed, there is little doubt that James’s testimony was the centerpiece of the prosecution’s case. Nearly all of the other evidence against Hayes was circumstantial. James was the only witness who testified that Hayes confessed to the mur *986 der and the burglary. The importance of this testimony cannot be understated. As the Supreme Court has observed: “A confession is like no other evidence. Indeed, ‘the defendant’s own confession is probably the most probative and damaging evidence that can be admitted against him.’ ” Arizona v. Fulminante, 499 U.S. 279, 296 , 111 S.Ct. 1246 , 113 L.Ed.2d 302 (1991) (quoting Bruton v. United States, 391 U.S. 123, 139-40 , 88 S.Ct. 1620 , 20 L.Ed.2d 476 (1968) (White, J., dissenting)).

Most importantly, James’s testimony was critical to the State’s burglary case, which was essential to both the first-degree murder conviction and the sentence. James testified that he went directly to his car without going to the office, that he did not participate in the burglary, and that the stolen property had already been placed in the car by Hayes. Hayes testified that he told James that he had killed Patel, that James went to investigate, and that Hayes next saw James burglarizing the office. Hayes’s version of events was partially corroborated by another occupant of the motel, Bearla May Wyatt, who testified that she saw James carrying things to Hayes’s car, “like he was moving out of an apartment.” The only witness other than James who testified that Hayes had spoken about a burglary was James’s girlfriend, Michele Gebert. However, she provided contradictory and confusing testimony, first denying on direct examination that Hayes had said anything about burglarizing the office, then testifying on redirect that he had. Most of Gebert’s information came from James, and she provided her version of events only after she and James had discussed it for many hours, deciding what to do.

The importance of James’s testimony was underscored by the prosecution in its closing argument, as it was in the defense closing. As defense counsel put it: “In this case, you can only conclude that Bluf-ford committed a robbery or a burglary if you believe Andrew James beyond a reasonable doubt.”

In sum, James’s testimony and credibility were crucial to the State’s case. Without it; there was only circumstantial evidence of the burglary, and only inference as to whether Hayes killed Patel “as a result of the commission of’ a burglary. That, coupled with the testimony about James’s moving items to the car, easily “could have affected the judgment of the jury.” Belmontes, 350 F.3d at 881 (citation and internal quotation marks omitted). Thus, under Napue and Alcorta , the false evidence presented was material to both the murder conviction and the imposition of the death penalty, and the habeas petition must be granted.

That the false evidence presented by the State dealt only with credibility does not change the materiality calculus. Noting that “[i]t is of no consequence that the falsehood bore upon the witness’ credibility rather than directly upon defendant’s guilt,” 360 U.S. at 269 , 79 S.Ct. 1173 (internal quotation marks omitted), the Supreme Court stated in Napue :

Id. In Giglio v. United States, 405 U.S. 150 , 92 S.Ct. 763 , 31 L.Ed.2d 104 (1972), the Supreme Court reversed a conviction *987 for Mooney-Napue error because the State had failed to disclose a promise made to its key witness that he would not be prosecuted if he testified for the government. Id. at 154-55 , 92 S.Ct. 763 .

It also does not matter that James was subject to impeachment on the basis of his transactional immunity, drug addiction, and criminal record. As the Supreme Court noted in Napue :

360 U.S. at 270 , 79 S.Ct. 1173 . For the jury’s determination of James’s credibility, James’s past criminal record and drug history were of little import, given that Ge-bert, Hayes, and James were all drug users with clouded histories. James’s credibility was measured in comparison to his peers. James’s transactional immunity was of no value because there was never any danger or suggestion that James would be charged in connection with this case. Unbeknownst to the jury, what was critical to James was immunity from prosecution for the pending felony charges. That was the factor that had made James reluctant to talk to the police in the first instance. Although James was not expressly told of the deal, it is quite evident that James should have known that something was afoot, because it was otherwise not logical for him to agree to be flown from Florida voluntarily into a jurisdiction in which he was facing outstanding charges. Yet, thanks to the careful machinations of the prosecution, James could deny the existence of any deal.

The disclosure of an additional, secret deal would not have been merely cumulative impeachment. It would have demonstrated that the State was going to great lengths to give James a powerful incentive to testify favorably, to the point of letting him go free on unrelated felony charges. Presumably, the importance to the State’s case of James’s testimony is what initially led the prosecution to make the secret deal; likewise, the importance to James’s credibility of his false testimony regarding the absence of a deal is what led the prosecution to endeavor to keep that deal secret. Thus, the State achieved the desired effect of artificially bolstering James’s credibility without taking the more overtly unconstitutional step: having James testify affirmatively, but falsely, that there was no deal protecting him from prosecution of other crimes.

If the jury had been informed of the critical deal, James’s credibility would have been affected. The jury was not permitted to assess whether James had an expectation of favorable treatment that could have affected his testimony because the State affirmatively placed false evidence before the jury that there was no deal. See Campbell v. Reed, 594 F.2d 4, 7 (4th Cir.1979) (noting that the fact that the defendant “was not aware of the exact terms of the plea agreement only increases the significance, for purposes of assessing credibility, of his expectation of favorable treatment”).

James would not have testified without the secret deal in place, because he was out of subpoena range and would not have been available for trial but for his agreement to be flown in for trial by the prosecution. Without the testimony of James, an entirely different trial would have occurred. If James had known of the secret deal and had testified about it, he would have been subject to impeachment — not only on the existence of the favorable deal, but also on the State’s attempts to keep the deal from the jury. The State could not have falsely buttressed his credibility *988 before the jury. Thus, the violation of Napue was material.

The violation of the State’s independent duty under Alcorta and Pyle was also material, . perhaps even more go. To avoid violating Hayes’s due process rights by allowing false evidence to go uncorrected, the State would have been forced to disclose to the jury after James testified that James’s testimony 'Concerning the lack of a deal was false; that a secret deal was in place concerning prosecution for the other crimes; and that "the State had solicited James’s testimony to the contrary knowing that he would be providing false evidence. Such a disclosure would have had a devastating effect on the credibility of the entire prosecution case. , It would have affected not only the special circumstance verdict, but also the jury’s ultimate decision to impose the penalty of death.- See, e.g., Silva v. Woodford, 279 F.3d 825 , 855 n. 25 (9th Cir.2002) (noting-in a capital case that “whatever doubts the jury may have entertained about [the defendant’s] culpability as a result of the undermining of [the key witness’s] credibility may also have affected their assessment of the appropriate penalty to impose”).

Thus, Hayes has satisfied the Napue/Alcorta/Agurs materiality standard, namely, whether there was any reasonable likelihood that the presentation of the false testimony or failure to correct the record once the false evidence was presented “could have affected the judgment of the jury.” Belmontes, 350 F.3d at 881 (citation and internal quotation marks omitted). The due process .violations have undermined our confidence in the verdict. Because the constitutional error was material, we must reverse the district court and direct the court to grant Hayes’s petition for a writ of habeas corpus.

IV

In closing, we must observe that this case is not merely about a peculiar circumstance. As we have noted, this is not the first time we have been confronted in recent years with schemes to place false or distorted evidence before a jury. Our criminal justice system depends on the integrity of the attorneys who present their cases to the jury. When even a single conviction is obtained through per-jurious or deceptive means, the entire foundation of our system of justice is weakened.

As we stated in Borne:

236 F.3d at 1096.

Wé reverse the judgment of the district court, and "remand with instructions to grant the petition for a writ of habeas corpus.

REVERSED AND REMANDED.

. We assume for purposes of our analysis that James was, in fact, unaware of the secret deal. But we note the distinct risk that, in preparing James for his testimony, James's counsel — who did know about the deal— might have influenced the content of that testimony, deliberately or not.

. To the extent that any of our prior case law, including Willhoite , suggests otherwise, those cases are overruled.

. The jury received two first degree murder instructions. The jury was first instructed that "[a]ll murder which is perp’etrated by any kind of. willful, deliberate and premeditated killing with express. malice aforethought is murder of the first degree.” The jury was also instructed as to felony murder, as follows: "The unlawful killing of a human being, whether intentional, unintentional or accidental, which occurs as a result of the commission of the crimes of robbery and/or burglary and where there was in the mind of the perpetrator the specific intent to commit such crime, is murder of the first degree.”

. The jury also found that Hayes committed murder during the commission of a robbery. However, the California Supreme Court overturned the robbery-murder conviction and the robbery special circumstance.