Appellant Chris Francis Williams appeals the district court’s denial of his petition for writ of habeas corpus. Williams challenges under the Ex Post Facto Clause the state court’s application of an amended version of California Penal Code § 654. The amended statute eliminated judicial discretion to impose a lower sentence afforded by the version in place at the time of Williams’ offense. We hold that application of the amended statute was an ex post facto violation.

Further, under our case law, such an error requires reversal without inquiring into its harmfulness. We therefore conditionally grant the writ of habeas corpus and remand.

FACTS

The indictment against Williams contained nine counts based on three separate incidents. Counts 1 and 2 (robbery) and counts 3, 4, and 5 (kidnaping for robbery) stemmed from a June 1996 incident at a Kragen Auto Parts Store in San Bernardi-no. Williams entered the store, pointed a gun at the clerk, and stated “This is a robbery” and “Give me all the money.” After the clerk put money into a box, Williams instructed another employee to carry the box and forced him and two other employees to accompany Williams approximately 200 yards to a parking lot. Williams then took the box and ordered the employees to walk back to the store.

Count 6 (robbery) and counts 7 and 8 (kidnaping for robbery) were based on a July 1996 incident at a San Bernardino Radio Shack. Williams showed a gun to two men working at the store and told them it was a robbery. One of the two employees put money from the register into a box and, at Williams’ direction, the two accompanied him approximately 200 hundred feet down the street. Williams then took the box from the employee holding it and instructed the two to return to the store.

An August 1996 incident gave rise to count 9 of the indictment (robbery). Williams entered a Redlands Kragen Auto Parts store, pointed a gun at the clerk, and directed him to open the safe. The clerk placed money from the safe into a box, handed it to Williams, and let Williams out of the store.

PROCEDURAL BACKGROUND

Williams was convicted in San Bernardi-no County Superior Court on four counts of robbery and five counts of kidnaping for robbery. The court sentenced him to two consecutive life terms and a consecutive determinate term, of 27 years. On appeal, the California Court of Appeal held that the trial court violated California Penal Code § 654, by imposing separate sentences for robbery and kidnaping for robbery convictions based on the same act. The Court of Appeal stayed the sentence on the pertinent robbery counts, which carried lower penalties than the corresponding kidnaping counts, and affirmed the rest of the judgment. The trial court then modified Williams’ sentence to two life sentences with possibility of parole plus 11 years and four months. The court sentenced Williams under the amended version of § 654, which provided that an act punishable under different provisions of law could only be punished under one of those provisions. The amended statute also required the court to impose the sentence for the count carrying a higher sentence when multiple counts were based on the same act. The California Supreme Court denied Williams’ petition for review. The San Bernardino County Superior Court subsequently denied Williams’ petition for a writ of habeas corpus. He then filed a habeas petition in the Court of Appeal, which was also denied. The California Supreme Court also denied a subsequent habeas petition.

Williams then filed this federal habeas petition, which the district court denied. Williams filed a timely notice of appeal, but the district court denied Williams a certificate of appealability (“COA”). We subsequently issued a COA limited to the question of whether the state trial court’s application of the amended version of California Penal Code § 654, violated Williams’ rights under the Ex Post Facto clause.

ANALYSIS

We review de novo a district court’s denial of a 28 U.S.C. § 2254 habeas petition. Campbell v. Rice, 408 F.3d 1166, 1169 (9th Cir.2005). Because Williams’ federal petition was filed after the effective date .of the Antiterrorism and Effective Death Penalty Act of 1996 (“AEDPA”), the AEDPA’s provisions apply. Id. The AED-PA limits a federal habeas court’s review of a state court’s decision to determining whether it was: “(1) contrary to, or involved an unreasonable application of, clearly established Federal law, as determined by the Supreme Court of the United States; or (2) based on an unreasonable determination of the facts in light of the evidence presented in the State court proceeding.” Id. at 1170 (quoting 28 U.S.C. § 2254 (d)(l)-(2)) (internal quotation marks omitted); see Lockyer v. Andrade, 538 U.S. 63, 70-73 , 123 S.Ct. 1166 , 155 L.Ed.2d 144 (2003) (explaining this standard). The question in Williams’ case is whether, at the time the state trial court imposed sentence under the amended version of § 654, the holdings of the Supreme Court established governing legal principles dictating that it do otherwise. See Andrade, 538 U.S. at 71-72 , 123 S.Ct. 1166 .

I. Ex Post Facto Violation

When the state court resentenced Williams, the Supreme Court had considered the application of the Ex Post Facto Clause to state statutes in two cases similar to this one. In Lindsey v. Washington, 301 U.S. 397 , 57 S.Ct. 797 , 81 L.Ed. 1182 (1937), the Court found an ex post facto violation because the petitioners had been sentenced under a law making mandatory what had been the maximum term for their offense when they committed the crime. The Lindsey petitioners were convicted of grand larceny. Id. at 397 , 57 S.Ct. 797 . At the time of the offense, the penalty for grand larceny was imprisonment for not more than 15 years. Id. at 397-98 , 57 S.Ct. 797 . The statute permitted the imposition of a sentence up to the maximum term and also set a minimum sentence of not less than six months or more than five years. Id. at 398 , 57 S.Ct. 797 . Once the prescribed minimum sentence elapsed, a parole board could order the prisoner released on parole. Id. A statute enacted after commission of the offense, but before petitioners’ sentencing, required the judge to impose the maximum term provided by law. Id. It also empowered the parole board to determine the length of each prisoner’s confinement up to the maximum term. Id. at 398-99 , 57 S.Ct. 797 . Thus, under the law in effect at the time of the offense, the petitioners could have been sentenced to a maximum term of less than 15 years. Id. at 400 , 57 S.Ct. 797 . The intervening change in law required that they receive a 15-year sentence during which the parole board had the discretion to grant supervised release. Id. The Lindsey court reasoned that such “an increase in the possible penalty is ex post facto, regardless of the length of the sentence actually imposed, since the measure of punishment prescribed by the later statute is more severe than that of the earlier.” Id. at 401 , 57 S.Ct. 797 (citations omitted).

Weaver v. Graham, 450 U.S. 24 , 101 S.Ct. 960 , 67 L.Ed.2d 17 (1981), held a Florida statute unconstitutional as applied to a petitioner who committed his crime before its enactment. The statute diminished the number of “gain-time” credits that prisoners could earn for good behavior. Id. at 25-26 , 101 S.Ct. 960 . Such credits reduced the portion of a prisoner’s sentence that he would be required to serve. Id. In finding an ex post facto violation, Weaver identified two critical elements of an ex post facto law: “it must be retrospective, that is, it must apply to events occurring before its enactment, and it must disadvantage the offender affected by it.” Id. at 29 , 101 S.Ct. 960 . The court reasoned that the statute substantially altered the consequences attached to the petitioner’s already-completed crime and that it disadvantaged him by lengthening the time he would have to stay in prison. Id. at 33 , 101 S.Ct. 960 .

The reasoning of Lindsey and Weaver dictate application of the version of § 654 in effect when Williams committed his crimes. In March 2000, the trial court resentenced Williams under the amended version of § 654, which provided that: “An act or omission that is punishable in different ways by different provisions of law shall be punished under the provision that provides for the longest potential term of imprisonment, but in no case shall the act or omission be punished under more than one provision.” Cal. PemCode § 654 (2000). At the time Williams committed his crimes, § 654 provided that: “An act or omission which is made punishable in different ways by different provisions of this code may be punished under either of such provisions, but in no case can it be punished under more than one.” Cal. Pen. Code § 654 (1996).

Under the earlier version of § 654, the trial court had the discretion to sentence Williams for either of two crimes he was convicted of based on the same act, i.e., robbery or kidnaping for robbery. By contrast, the amended version of the statute required the trial court to sentence him for the crime carrying the higher penalty. Because the amended statute removed the judge’s discretion to impose a lighter sentence, applying it to Williams violated the Ex Post Facto Clause under Lindsey, 301 U.S. at 401 , 57 S.Ct. 797 , and Weaver, 450 U.S. at 29 , 101 S.Ct. 960 . The state trial court’s application of the amended version of § 654 was thus contrary to clearly established Supreme Court precedent.

II. Applicability of Harmless Error Analysis

The State argues that the ex post facto violation resulting from application of the amended version of § 654 was harmless error. It suggests that we should apply the Brecht standard of harmless error review, determining whether the ex ipost facto error had a “substantial and injurious effect” on the judgment. See Brecht v. Abrahamson, 507 U.S. 619 , 632 n. 7, 638, 113 S.Ct. 1710 , 123 L.Ed.2d 353 (1993). Under the Brecht standard, a trial-type constitutional error is harmless unless it has a “substantial and injurious effect or influence in determining the jury’s verdict.” Id. The ex post facto error at issue here, however, occurred at sentencing — not during trial' — -when the court applied the amended version of § 654. It is thus not a trial-type error that would affect a jury’s verdict. Accordingly, we reject the State’s contention that an ex post facto violation is a “trial-type” error subject to Brecht harmless error analysis.

We turn, instead, to our case law which specifically addresses ex post facto violations. The Supreme Court has noted that “[t]he proper relief upon a conclusion that a state prisoner is being treated under an ex post facto law is to remand to permit the state court to apply, if possible, the law in place when his crime occurred.” Weaver, 450 U.S. at 36 n. 22, 101 S.Ct. 960 ; see also Murtishaw v. Woodford, 255 F.3d 926, 967 (9th Cir.2001). In Murtishaw , after concluding that “[t]aking discretion away from a sentencer violates the Ex Post Fac-to clause,” id. at 965 , we reversed the petitioner’s death sentence and remanded for resentencing under the proper statute. Id. at 967, 974 . We did not apply harmless error analysis to the ex post facto violation. Id.

Thus, in Murtishaw , we implicitly concluded that an ex post facto sentencing violation which results in taking away the sentencer’s discretion is the type of error which has a substantial and injurious effect on the sentence or, at the least, was the type of error as to which we could not determine with any degree of confidence whether it had a substantial effect on the sentence. Cf. O’Neal v. McAninch, 513 U.S. 432, 445 , 115 S.Ct. 992 , 130 L.Ed.2d 947 (1995) (concluding that, with respect to trial-type error, “when a habeas court is in grave doubt as to the harmlessness of an error that affects substantial rights, it should grant relief’); United States v. Ameline, 409 F.3d 1073, 1079 (9th Cir.2005) (en banc) (“Rather than affirm a sentence that was unconstitutional and may have been prejudicial, we elect to remand to the district court to answer the question whether the sentence would have been different had the court known that the Guidelines were advisory.”); id. at 1081 (noting that “it is a miscarriage of justice to give a person an illegal sentence” (quoting United States v. Paladino, 401 F.3d 471 , 483(7th Cir.2005))).

Our cases following Murtishaw are also consistent in their view that a showing of harm or prejudice from an ex post facto violation is not required as a precondition to habeas relief. See Brown v. Palmateer, 379 F.3d 1089, 1091, 1096 (9th Cir.2004) (holding that postponement of a habeas petitioner’s parole date pursuant to a statutory amendment enacted after the commission of his crime violated the Ex Post Facto Clause and, accordingly, reversing the denial of his habeas petition without conducting a harmless error analysis); Hunter v. Ayers, 336 F.3d 1007, 1011-13 (9th Cir.2003) (holding that the application of an amended prison regulation to deny restoration of good time credits constituted an ex post facto violation and affirming habeas relief without conducting a harmless error analysis); Himes v. Thompson, 336 F.3d 848, 864 (9th Cir.2003) (concluding that an ex post facto violation occurred when the parole board subjected a habeas petitioner to parole regulations that were more onerous than those in place at the time he committed his offense and granting habeas relief without conducting a harmless error analysis). In short, given an ex post facto sentencing violation, our case law is clear and consistent that Williams is entitled to habeas relief.

CONCLUSION

The district court’s denial of Williams’ petition for a writ of habeas corpus is reversed and the case is remanded to the district court with instructions to grant the writ, unless the State resentences Williams under the applicable version of § 654 within a reasonable period of time to be determined by the district court.

REVERSED and REMANDED.

. While conceding that a "technical” ex post facto violation occurred, the State suggests that Lindsey was not "clearly established” federal law at the time of sentencing because its "viability has been questioned,” citing Barnes v. Scott, 201 F.3d 1292, 1294-95 (10th Cir.2000). Baines refers to a footnote in the Supreme Court's opinion in Cal. Dep't of Con. v. Morales, 514 U.S. 499 , 115 S.Ct. 1597 , 131 L.Ed.2d 588 (1995), which states: Our opinions in Lindsey, Weaver, and Miller suggested that enhancements to the measure of criminal punishment fall within the ex post facto prohibition because they operate to the "disadvantage” of covered offenders. But that language was unnecessary to the results in those cases and is inconsistent with the framework developed in Collins v. Youngblood. After Collins, the focus of the ex post facto inquiry is not on whether a legislative change produces some ambiguous sort of "disadvantage,” nor, as the dissent seems to suggest, on whether an amendment affects a prisoner’s "opportunity to take advantage of provisions for early release,” but on whether any such change alters the definition of criminal conduct or increases the penalty by which a crime is punishable. Id. at 506 n. 3, 115 S.Ct. 1597 (citations omitted). Morales , however, did not overrule Lindsey and Weaver , but distinguished them by pointing out that the laws there at issue "had the purpose and effect of enhancing the range of available prison terms.” Id. at 507, 115 S.Ct. 1597 . . The Supreme Court has also identified a narrow category of constitutional errors that is not subject to harmless error analysis. See Nederv. United States, 527 U.S. 1, 8 , 119 S.Ct. 1827 , 144 L.Ed.2d 35 (1999) (noting that structural errors requiring automatic reversal include: a complete denial of counsel; a biased trial judge; racial discrimination in the selection of a grand jury; denial of self-representation at trial; denial of a public trial; and a defective reasonable doubt instruction). But just as the ex post facto violation here cannot be categorized as a "trial-type” error, it also cannot be categorized as a "structural” error which affects the structure of a trial. . We did, however, apply Brecht harmless error analysis to a jury instruction error re-suiting from application of the ex post facto statute, identifying jury instruction error as a "trial-type error that occurred during the presentation of the case to the jury.” Murtishaw, 255 F.3d at 973. . We also note that the State's countervailing interest in finality is much less weighty with respect to resentencing, as opposed to retrial, at least in the non-capital context.