Under Arizona law, a conviction for first-degree murder can be based on either or both of two theories: premeditated murder (an intentional, planned killing) or felony murder (a killing that results from the intentional commission by defendant of another felony, but which does not necessarily involve an intent to kill). Michael Evanchyk was tried in Arizona state court, together with other defendants, for multiple crimes in connection with events that resulted in a death. He was acquitted by a jury of first-degree murder and of burglary, but was convicted of second-degree murder and of conspiracy to commit first-degree murder. He petitioned the district court for habeas corpus relief under 28 U.S.C. § 2254 , challenging only the conviction for conspiracy to commit first-degree murder. The district court granted his petition conditionally, subject to the State of Arizona’s ability to retry him on that charge. The district court held that under the instructions given to the jury, Evanchyk could have been convicted for, in effect, conspiracy to commit felony murder, which is not a crime under Arizona law. The State appeals, contending that there was no instructional error and that any error was harmless, in any event. Evanchyk cross-appeals, arguing that the district court’s conditional grant, permitting a re-trial, was erroneous on double jeopardy or collateral estoppel grounds, and also that the district court erroneously denied his ineffective assistance of counsel claim.

We affirm. In response to certified questions from the district court, the Arizona Supreme Court made clear that, under Arizona law, intent to kill is an essential element of the offense of conspiracy to commit first-degree murder. The instructions given in this case permitted the jury to convict Evanchyk of that offense without requiring a finding of that essential element, an intent to kill. This constitutes a violation of Evanchyk’s federal constitutional right to due process. The circumstances do not permit us to find that the error in this case was harmless, so habeas relief is appropriate. At the same time, because there was substantial evidence to support the State’s allegation of an agreement to kill, with the required intent, it is appropriate to permit the State to re-try Evanchyk on the conspiracy charge, if it so decides.

I.BACKGROUND

The district court adopted the description of the crime set forth in the Arizona Court of Appeals’ decision affirming Evan-chyk’s conviction on direct appeal:

State v. Evanchyk, No. 2 CA-CR-94-0533, mem. dec., at 2-3 (1996) (“Evanchyk I”).

The State charged Evanchyk with first-degree murder, first-degree burglary, and conspiracy to commit first-degree murder. He was tried together with Ybarra, Olson and another co-defendant in Pima County Superior Court. At the close of trial, the judge instructed the jury on first-degree murder, second-degree murder, manslaughter, burglary, and conspiracy to commit first-degree murder.

The instruction regarding the elements of conspiracy to commit first-degree murder read as follows:

The crime of first-degree murder was defined as either of the following two alternatives: (1) when “defendant intended or knew that he would cause the death of another ... with pre-meditation” or (2) when someone “commits or attempts to commit burglary and in the course of, and in furtherance of such offense, or imediate [sic] flight from such offense, such person, or another person, causes the death of any person. This type of murder requires no mental state other than that which required for [sic] the commission of the offense of burglary.”

The instructions given to the jury by the trial judge explicitly reiterated that a conviction for first-degree murder could be based on a felony murder theory that did not require, the jury to find an intent to kill, only an intent to commit burglary:

As noted above, the jury found Evan-chyk not guilty of first-degree burglary and first-degree murder, but guilty of second-degree murder and conspiracy to commit first-degree murder. He was sentenced to concurrent prison terms of 25 years for conspiracy to commit first-degree murder and 15 years for second-degree murder. The same jury reached somewhat different verdicts for co-defendants Olson and Ybarra. They were both found guilty of first-degree murder, burglary, and conspiracy to commit first-degree murder. According to the verdict forms, which required the jurors to identify the basis for a first-degree murder conviction as either or both of felony murder and premeditated murder, by checking lines on a typed form, 11 jurors based their conviction for Olson on a felony murder theory alone and 1 juror found Olson guilty of both premeditated and felony murder. All 12 based Ybarra’s conviction on felony murder.

On direct review, the Arizona Court of Appeals affirmed Evanchyk’s conviction, concluding that there was substantial evidence to support the guilty verdict on the conspiracy charge. The Arizona Supreme Court denied review.

Evanchyk then filed for state collateral relief, arguing that he was convicted of a conspiracy to commit first-degree murder based on a legally invalid theory, i.e., conspiracy to commit felony murder. He argued further that he had been denied effective assistance of trial and appellate counsel because his lawyers had failed to challenge the conspiracy instruction on this basis. The Arizona Court of Appeals denied relief, holding that “it need not answer the theoretical question whether conspiracy to commit first degree murder may be based on felony murder because on [direct] appeal we concluded there was substantial evidence of an agreement among the co-defendants to murder the victim.” State v. Evanchyk (“Evanchyk II”), No. 2 CA-CR-97-0505, mem. dec., at 2, ¶ 3 (1998). In a petition for review to the Arizona Supreme Court, Evanchyk argued that the Court of Appeals utilized the wrong standard of review on the post-conviction relief petition and that it substituted its judgment for that of the jury’s. The Arizona Supreme Court denied Evan-chyk’s petition.

Evanchyk then filed a petition for federal habeas relief in the district court. The district court initially held that habeas relief would be justified if in fact Evanchyk might have been convicted for activity that did not constitute a crime under Arizona law. The district court noted that:

Because Arizona law was not clear on whether conspiracy to commit first-degree murder could be based on the felony murder type of first-degree murder, the district court certified to the Arizona Supreme Court the following questions:

In Evanchyk v. Stewart, 47 P.3d 1114, 1119 (Ariz.2002) (“Evanchyk III”), the Arizona Supreme Court responded with the following:

The Arizona Supreme Court further explained that,

Id.

In light of the Arizona Supreme Court’s response in Evanchyk III, the district court granted habeas relief, consistent with its prior order certifying the questions to the Arizona Supreme Court. It held that the type of instructional error involved — which allowed for conviction on either a valid or an invalid theory where it was “impossible to tell from the verdict upon which theory the jury (or juror) relied” — required per se reversal such that the court “need not engage in harmless error analysis,” citing Suniga v. Bunnell, 998 F.2d 664, 668-69 (9th Cir.1993), and Ficklin v. Hatcher, 177 F.3d 1147, 1151 (9th Cir.1999). The court therefore vacated the conviction. Because the court agreed with the state courts that there was substantial evidence of a conspiracy to commit first-degree murder under the proper legal theory, it granted a conditional writ, subject to the State’s option to retry Evanchyk within a reasonable time.

II. DISCUSSION

A writ of habeas corpus may be issued when a prisoner “is in custody in violation of the Constitution or laws or treaties of the United States.” 28 U.S.C. § 2241 (c)(3) (2002). The Antiterrorism and Effective Death Penalty Act of 1996, 110 Stat. § 1214 (1996) (“AEDPA”), applies to Evanchyk’s petition because the petition was filed after April 24,1996. Under AEDPA, a writ may issue only if the state court’s ruling “resulted in a decision that was contrary to, or involved an unreasonable application of, clearly established Federal law, as determined by the Supreme Court of the United States” or was “based on an unreasonable determination of the facts in light of the evidence presented in the State court proceeding.” 28 U.S.C. § 2254 (d); see also Lockyer v. Andrade, — U.S. -, 123 S.Ct. 1166, 1172 , 155 L.Ed.2d 144 (2003). We review de novo the district court’s decision to grant habeas corpus relief. Suniga, 998 F.2d at 666 . “When considering an allegedly erroneous jury instruction in a habeas proceeding, an appellate court first considers whether the error in the challenged instruction, if any, amounted to ‘constitutional error.’ If so, the court then considers whether the error was harmless.” Morris v. Woodford, 273 F.3d 826, 833 (9th Cir.2001), ce rt. denied, 537 U.S. 941 , 123 S.Ct. 341 , 154 L.Ed.2d 248 (2002) (citing Calderon v. Coleman, 525 U.S. 141, 145, 146 , 119 S.Ct. 500 , 142 L.Ed.2d 521 (1998) (per curiam)).

A. Due Process

It is a violation of due process for a jury instruction to omit an element of the crime. United States v. Gaudin, 515 U.S. 506, 509-10 , 115 S.Ct. 2310 , 132 L.Ed.2d 444 (1995); Osborne v. Ohio, 495 U.S. 103 , 122-24 & n. 17, 110 S.Ct. 1691 , 109 L.Ed.2d 98 (1990); Sandstrom v. Montana, 442 U.S. 510, 521-24 , 99 S.Ct. 2450 , 61 L.Ed.2d 39 (1979); In re Winship, 397 U.S. 358, 364 , 90 S.Ct. 1068 , 25 L.Ed.2d 368 (1970); Ho v. Carey, 332 F.3d 587, 595 (9th Cir .2003) (omitted mens rea element is a due process violation); Keating v. Hood, 191 F.3d 1053, 1061 (9th Cir.1999) (same); United States v. Mendoza, 11 F.3d 126, 128 (9th Cir.1993) (“[W]hen a trial judge omits an element of the offense charged from the jury instructions, it deprives the jury of its fact-finding duty and violates the defendant’s due process rights.”). The instructions on conspiracy to commit first-degree murder omitted the element of intent to kill. Nowhere does the instruction say that intent to kill or premeditation is required. Rather, it refers to the conspired crime as “conduct” which constitutes “first-degree murder.”

In a case where felony murder was not a viable theory of first-degree murder — that is, where first-degree murder could only be of the premeditated variety — the conspiracy instruction used here would not pose a problem. In such a case, it would be unequivocal that the “conduct” cross-referenced in the conspiracy instruction was the conduct identified in the one and only first-degree murder theory. In this case, however, where felony murder was argued as a basis to find first-degree murder, the generic conspiracy instruction was insufficient. By defining “first-degree murder” as either premeditated murder or felony murder, and then, in the separate conspiracy instruction, defining “conspiracy to commit first-degree murder” in generic terms as a conspiracy to engage in “conduct” which constitutes “first-degree murder,” the instructions could cause a jury to rely upon felony murder as the predicate offense for the conspiracy conviction.

For example, the jury could have concluded that Evanchyk and his coconspirators agreed to commit a burglary and that during that burglary Harris’s death occurred. If one or more of the jurors took this route, as opposed to finding an agreement to kill, this would mean that Evanchyk was convicted for conspiracy to commit first-degree murder even though the jury did not unanimously find intent to kill — a necessary element of the crime in Arizona. Accordingly, because felony murder was a theory of first-degree murder in this case, the generic conspiracy instruction omitted the element of intent to kill and, therefore, violated Evanchyk’s due process rights.

When presented with this issue, the Arizona Court of Appeals, in Evanchyk II, failed to apply the correct controlling authority. Its decision was thus contrary to clearly established federal law as determined by the Supreme Court. Clark v. Murphy, 331 F.3d 1062, 1067 (9th Cir. 2003) (citing Williams v. Taylor, 529 U.S. 362, 413-14 , 120 S.Ct. 1495 , 146 L.Ed.2d 389 (2000)). Rather than acknowledge a due process violation, the Court of Appeals reasoned that so long as a reasonable jury could have found Evanchyk guilty of the valid crime, it did not matter that the instructions also allowed for conviction on a theory that lacked the necessary element of intent to loll. In its own words, the court said that it “need not answer the theoretical question whether conspiracy to commit first degree murder may be based on felony murder because on appeal we concluded there was substantial evidence of an agreement among the co-defendants to murder the victim.” This reasoning, which would affirm a conviction so long as there is substantial evidence to support a conviction on the valid legal theory, is without question contrary to clearly established federal law holding that an instruction omitting an essential element is a constitutional violation. Gaudin, 515 U.S. at 509-10 , 115 S.Ct. 2310 ; Osborne, 495 U.S. at 122 -24 & n. 17, 110 S.Ct. 1691 ; Sandstrom, 442 U.S. at 521-24 , 99 S.Ct. 2450 . In the face of such an error, the court may sustain the conviction only if it can satisfy itself that the error is harmless. Neder v. United States, 527 U.S. 1, 8-11 , 119 S.Ct. 1827 , 144 L.Ed.2d 35 (1999). The Court of Appeals’ conclusion that there was “substantial evidence” to support the relevant conviction falls well short of that standard.

B. Harmless Error

Although it is a due process violation for jury instructions to omit an essential element of a crime, that is a type of error which is subject to harmless error review, as noted above. Id. (holding that jury instructions that omit element(s) of a crime do not pose a “structural defect,” requiring automatic reversal, but rather are “trial errors,” subject to harmless error review); Keating, 191 F.3d at 1062 (omitted mens rea element is a due process violation, but is subject to harmless error review); Ho, 332 F.3d at 595 (same). “Habeas petitioners are not entitled to relief unless they can establish that the error resulted in ‘actual prejudice.’ ” Id. (quoting United States v. Lane, 474 U.S. 438, 449 , 106 S.Ct. 725 , 88 L.Ed.2d 814 (1986)). “Actual prejudice” means that the error “had a ‘substantial or injurious effect or influence in determining the jury’s verdict.’ ” Id. (quoting Brecht v. Abrahamson, 507 U.S. 619, 637 , 113 S.Ct. 1710 , 123 L.Ed.2d 353 (1993)); see also California v. Roy, 519 U.S. 2, 4-6 , 117 S.Ct. 337 , 136 L.Ed.2d 266 (1996) (per curiam) (holding that, on habeas review, Brecht’s harmless error standard applies to jury instructions that omit an element of the crime). “ ‘If we are in grave doubt as to whether the error had such an effect, the petitioner is entitled to the writ.’” Ho, 332 F.3d at 595 (quoting Coleman v. Calderon, 210 F.3d 1047, 1051 (9th Cir. 2000)).

It is reasonably probable that the failure to identify intent to kill as a necessary element of the conspiracy charge “substantially] ... influence^]” the verdict. Brecht, 507 U.S. at 639 , 113 S.Ct. 1710 (first alteration and ellipsis in original). At the least, we are “in grave doubt” as to whether the error resulted in Evanchyk being convicted without the jury having first found intent to kill. Coleman, 210 F.3d at 1051 .

The State argues that there was overwhelming evidence that Evanchyk and his coconspirators made an agreement to kill Harris, and therefore that any error must have been harmless. But the verdicts reached by the same jury with respect to the other defendants make it impossible for us to conclude with confidence that the jury would have convicted Evanchyk of conspiracy to commit first-degree murder, if properly instructed that intent to kill was an essential element of that crime.

Both Olson and Ybarra were convicted of first-degree murder, as well as of conspiracy to commit first-degree murder. According to the verdict forms, though, 11 jurors based Olson’s murder conviction on a theory of felony murder and only one juror found Olson guilty of both premeditated and felony murder. All 12 based Ybarra’s conviction on felony murder. Felony murder does not require a finding of intent to kill. The jury was specifically instructed that only an intent to commit burglary was required. With one lone exception, the jurors did not find the other defendants guilty of murder on a theory of premeditated murder, which entailed finding an intent to kill. We recognize that this verdict does not necessarily mean that the jurors affirmatively concluded that there was no intent to kill on the part of any of the defendants. It is possible that, having reached agreement on a felony murder theory, sufficient to support the first-degree murder convictions of Olson and Ybarra, the jurors simply decided not to take the time to grapple with the alternative premeditation theory. But we are simply unable to conclude, in the face of this record, that the failure to instruct the jury that intent to kill was a necessary element of conspiracy to commit first-degree murder was harmless error. We cannot be reasonably certain that the jury would have found intent to kill on the part of Evanchyk, if required to do so. Because we are left with grave doubt about that, the conviction cannot be defended on the basis of harmless error.

C. Evcmchyk’s Cross-Appeal

Evanchyk argues that re-trial should be barred by collateral estoppel or by double jeopardy principles. He insists that because he was acquitted of first-degree premeditated murder, he cannot now be found to have premeditated. We disagree. The Arizona Supreme Court explicitly held that an acquittal on first-degree murder does not preclude a conviction for conspiracy to commit first-degree murder. Evanchyk III, 47 P.3d at 1119 (“the defendant may be convicted of conspiracy to commit first-degree murder even though he or a coconspirator is convicted of nothing else or nothing more than second-degree murder”). The offense of conspiracy can be committed without (or completed before) the actual commission of the underlying crime, in this case murder. Thus, a verdict would not necessarily be “inconsistent” if a jury convicted on eon-spiracy to commit first-degree murder but acquitted on first-degree murder itself, choosing instead to convict for second-degree murder. Even if the verdict were inconsistent, however, that would be irrelevant, so long as we could be confident that the verdicts were in fact premised on properly instructed crimes. See United States v. Powell, 469 U.S. 57, 65 , 105 S.Ct. 471 , 83 L.Ed.2d 461 (1984) (holding that the Constitution tolerates inconsistent verdicts).

We agree with the district court and the state courts that the record reflects more than ample evidence to support a conviction for conspiracy to commit first-degree premeditated murder. The evidence reflects that the murder was committed within days of an attack on Evanchyk by the victim. On the day of Harris’s death, Evanchyk and his friends repeatedly made threats to Harris and Harris’s girlfriend, threatening to kill Harris. Evanchyk even banged on Harris’s window earlier in the day and said “[C]ome out, we want to kill you.” He had also boasted about his desire to get even with Harris, and told Harris, while hammering a wooden cross into the ground, that this was his headstone. He also told Harris’s girlfriend that she would have to bury another one of her men (one of her prior boyfriends apparently had been killed). Accordingly, the district court’s conditional grant of the writ, subject to re-trial, was proper because there was substantial evidence of an agreement to kill. See Lockhart v. Nelson, 488 U.S. 33, 38 , 109 S.Ct. 285, 102 L.Ed.2d 265 (1988) (the constitutional prohibition against successive prosecutions does not prevent the State from retrying a defendant who succeeds in getting his first conviction set aside because of trial error).

III. CONCLUSION

The instructions given by the trial court permitted the jury to convict for conspiracy to commit first-degree murder without finding intent to kill. The Arizona Supreme Court has explicitly held that intent to kill is an essential element of the crime. Thus, Evanchyk’s federal right to due process was violated. We cannot conclude that the error was harmless. The state court’s decisions, affirming Evanchyk’s conviction and denying his habeas petition, were contrary to clearly established federal law as determined by the Supreme Court. We therefore affirm the district court’s judgment granting habeas relief under 28 U.S.C. § 2254 (d).

AFFIRMED.

. Under Arizona law, first-degree murder is a unitary crime, and a defendant can be convicted even though the jurors are not unanimous on the theory, i.e., premeditated murder or felony murder. State v. Schad, 163 Ariz. 411 , 788 P.2d 1162, 1168 (1989). Submitting a multi-theory crime to the jury without requiring unanimity on any one predicate theory is not a constitutional violation. Schad v. Arizona, 501 U.S. 624, 644-45 , 111 S.Ct. 2491 , 115 L.Ed.2d 555 (1991). . Evanchyk argues that harmless error analysis would be inappropriate here and that automatic reversal is required, citing Suniga, 998 F.2d 664 ; Yates v. United States, 354 U.S. 298, 312 , 77 S.Ct. 1064 , 1 L.Ed.2d 1356 (1957), overruled on other grounds by Burks v. United States, 437 U.S. 1, 2 , 98 S.Ct. 2141 , 57 L.Ed.2d 1 (1978); Stromberg v. California, 283 U.S. 359 , 51 S.Ct. 532 , 75 L.Ed. 1117 (1931); Schad, 501 U.S. 624 , 111 S.Ct. 2491 , 115 L.Ed.2d 555 ; and Griffin v. United States, 502 U.S. 46 , 112 S.Ct. 466 , 116 L.Ed.2d 371 (1991). We disagree. Those cases involved jury instructions for crimes based on facially invalid or legally impossible theories, or "non-existent” crimes. In contrast, conspiracy to commit first-degree murder is a legitimate and valid crime under Arizona law. . We note that Ninth Circuit case law has not always used the same language in describing the harmless error standard in federal habeas cases. While we have referred to Brecht’s "substantial and injurious influence" standard, see, e.g., Ho, 332 F.3d at 595 , we have also said that where an instruction omits an element, and there is a general verdict such that we cannot tell on which legal theory the jury relied, the error cannot be harmless unless 'it is absolutely certain’ that the jury relied upon the legally correct theory to convict[.]” Keating, 191 F.3d at 1063 (quoting Ficklin v. Hatcher, 177 F.3d 1147, 1151 (9th Cir.1999) (emphasis in original)). In Mancuso v. Olivarez, we noted "that our prior decisions [citing Keating as one of them] have not consistently interpreted or applied the Brecht standard.” 292 F.3d 939 , 950 n. 4 (9th Cir.2002). In the instant case we conclude that, under either articulation, we cannot say that the omitted element was harmless. For the reasons detailed below, the omitted element did "substantially] ... influence” the verdict, Brecht, 507 U.S. at 637 , 113 S.Ct. 1710 , and a fortio-ri, under Keating , we cannot be " 'absolutely certain’ that the jury did not rely on the legally erroneous ... theory[.]” 191 F.3d at 1063 . . Because we affirm habeas relief on due process grounds, we do not need to reach Evanchyk’s ineffective-assistance-of-counsel claim. . The Arizona Court of Appeals, in Evanchyk II, also suggested that relief would be properly denied because this case was simply a situation of inconsistent verdicts, which is insufficient to grant habeas relief. But the problem here is more fundamental than that. As outlined above, because the jury was not instructed that it had to find an intent to kill in order to convict for conspiracy to commit first-degree murder, we cannot tell whether the jury actually found the element. The jury’s other verdicts do not permit us to fill in that gap and conclude that the error was harmless. Our decision does not rest on any perceived '‘inconsistency” within the jury's verdicts.