Earnest Bray, Jr. and Richard Napoleon Brown were each convicted of petty theft, Bray for attempting to steal three videotapes and Brown for attempting to steal a steering wheel alarm. Because of prior convictions, each was sentenced to life without possibility of parole for 25 years. Each now appeals the denial of a habeas petition contending that his sentence constituted cruel and unusual punishment in violation of the Eighth Amendment.
This court recently held, in Andrade v. Attorney General of the State of California, 270 F.3d 743 (9th Cir.2001), that a 50-year-to life sentence for two petty theft convictions violated the Eighth Amendment’s prohibition against cruel and unusual punishment, and that the California Court of Appeal unreasonably applied clearly established United States Supreme Court law when it held otherwise. Id. at 747. Because these cases are indistinguishable from Andrade in any material respect, we similarly hold that the California Court of Appeal decisions upholding 25-year-to-life sentences for petty theft were contrary to and unreasonable applications of clearly established Supreme Court law. Like Andrade, “[o]ur decision *1021does not invalidate California’s Three Strikes law generally.” Id.
I. BACKGROUND
A. Provisions of The California Three Strikes Law
As Andrade summarizes in detail the pertinent background and features of California’s so-called three strikes law (“Three Strikes”), Cal.Penal Code §§ 667(b)-(i) and 1170.12, we do so only briefly here. See 270 F.3d at 747-48. Unless otherwise stated, all statutory citations are to the California Penal Code.
A defendant with two or more prior “strikes” — that is, certain felony convictions — who is convicted of a felony must be sentenced under the Three Strikes statute to no less than 25 years to life, § 667(e)(2)(A), and cannot receive “good time credits” to reduce his sentence below the mandatory minimum term of 25 years. In re Cervera, 24 Cal.4th 1073, 103 Cal.Rptr.2d 762, 16 P.3d 176, 181 (2001). Only “serious” felonies, see § 1192.7(c), or “violent” felonies, see § 667.5(c), count as prior strikes. § 667(d)(1). The current offense that triggers the Three Strikes penalties, however, may be any felony under California law. § 667(e)(2)(A). It is this latter feature that led to life sentences for minor thefts in Andrade and in these cases.
Petty theft — theft of goods or money worth less than $400, §§ 487, 488 — is a misdemeanor, carrying a maximum sentence of 6 months in jail, § 490. Petty theft “with a prior” — that is, when committed after a conviction and time served for petty theft, grand theft, auto theft, burglary, carjacking, robbery, or receiving or concealing stolen property — is punishable either as a misdemeanor with up to one year in county jail or as a felony with up to three years in state prison. §§ 666, 496,18.
A conviction of petty theft with a prior as a felony can count as the triggering offense for purposes of Three Strikes, People v. Terry, 47 Cal.App.4th 329, 54 Cal.Rptr.2d 769, 770-71 (1996), leading to two unusual features of California recidivism law. First, the “core conduct” of petty theft with a prior “is, in the first instance, classified as a misdemeanor rather than a felony.” Andrade, 270 F.3d at 760. Where petty theft with a prior results in a felony conviction, the petty theft offender’s recidivism can be “double counted,” so as initially to transform the misdemeanor of petty theft into a felony and then to count it as the basis for a life sentence. Id. at 759-60; see also Riggs v. California, 525 U.S. 1114, 119 S.Ct. 890, 142 L.Ed.2d 789 (1999) (Stevens, J., memorandum opinion respecting the denial of the petition for writ of certiorari).
Second, if petty theft is committed after multiple prior convictions for non-theft offenses, including serious and violent offenses, then the petty theft must be charged as a misdemeanor and cannot trigger Three Strikes’ enhancements. See § 666. So, for example, if Bray’s or Brown’s prior convictions had all been for assault or manslaughter, neither could have been sentenced to 25 years to life for his petty theft conviction; only a six-month misdemeanor sentence would have been possible. See § 490, 666.
B. Facts and Procedural History
1. Bray v. Ylst
a. Bray’s Principal Offense
On March 28, 1994, Bray attempted to steal three videotapes from a music and video store in a Long Beach, California shopping mall. He activated the store’s alarm system when he tried to leave, and the store’s clerks detained him and turned him over to mall security. When the police arrived and arrested Bray, they confiscated a plastic bag containing the videotapes.
*1022b. Bray’s Prior Convictions
In finding Bray guilty for the theft of the videotapes, the jury also found that he had been convicted of four previous felony offenses.1 In February 1980, Bray was convicted on three separate counts of robbery, § 211. The first two convictions stemmed from one August 1979 incident in which Bray and a co-defendant stole a purse and a briefcase from the driver of a car. When the victim grabbed Bray, his co-defendant, who was brandishing a gun, pointed it at the driver’s head and threatened to kill her if she did not release Bray. The victim complied, but as Bray and the co-defendant fled the scene, the co-defendant fired three shots.
The third robbery conviction stemmed from a separate incident in which Bray and several co-defendants approached the victim and demanded his watch. One co-defendant then hit the victim in the face and took the watch. After the victim fell to the ground, a second co-defendant kicked him in the face and took five dollars in cash. The court sentenced Bray to three years in prison for each of the three convictions, the sentences to run concurrently. After 21 months, he was released on a work furlough.
The jury also found that in November 1987, Bray was again convicted of robbery. The court sentenced Bray to three years in prison, but he was paroled approximately 18 months later.
c. Prior Proceedings
Based on the presence of a prior theft conviction, Bray’s current petty theft offense was charged as a felony, § 666. The jury convicted Bray of the felony and returned “true” findings on the allegations that Bray had four prior serious or violent felony convictions and had served two pri- or prison terms. Because he was convicted for the current offense as a felony and the jury found two or more prior strikes, Bray was subject to the mandatory 25-year-to-life sentence provided by Three Strikes. At sentencing, the court rejected Bray’s argument that his punishment was cruel and unusual in violation of the Eighth Amendment. Bray appealed his sentence on the same grounds, but the California Court of Appeal rejected this contention in an unpublished opinion, and the California Supreme Court denied Bray’s petition for review.
Bray then filed a 28 U.S.C. § 2254 habe-as petition in district court. The magistrate judge issued a report concluding that Bray’s sentence did not violate the prohibition against cruel and unusual punishment. Adopting the magistrate judge’s reasoning, the district court denied Bray’s habeas petition. Although the district court denied Bray’s application for a Certifícate of Appealability (COA), this court granted a COA on the cruel and unusual punishment issue.2
*10232. Broum v. Mayle
a. Brown’s Principal Offense
On August 7, 1995, Brown attempted to shoplift a steering wheel alarm worth $25 from a Walgreens store. He picked up a few items in the store and left them on the counter, telling the clerk that he needed to go get his checkbook. He returned several hours later and brought a few more items to the counter. When the clerk asked if he had found his checkbook, he replied that he had. After questioning why the clerk kept watching him, he put the items down and stated that he did not want to buy anything from the store. When Brown tried to leave again, he set off the store’s alarm system. The clerk detained Brown and asked him to return what he had taken. He evidently refused. When security guards arrived, they found on Brown the steering wheel alarm with a security tag.3
b. Brovm’s Prior Convictions
Although Brown’s criminal history is somewhat longer than Bray’s and includes numerous convictions for misdemeanor offenses, Brown has a total of five serious or violent prior felony convictions:4 A 1971 conviction for two counts of second degree burglary, § 459; a 1976 conviction for two counts of assault with a deadly weapon, § 245; and a 1984 robbery conviction,5 § 211. The record does not reveal the underlying facts of these offenses.
c.Prior Proceedings
The jury found Brown guilty of petty theft with a prior, § 666. Brown had waived the right to have a jury determine whether his prior convictions were true, and the court found that he had been convicted of two prior strikes-the 1976 assault and the 1984 robbery. At sentencing, Brown moved to have the court strike the prior convictions on the grounds that a 25-year-to-life sentence would constitute cruel and unusual punishment. The court rejected the motion and sentenced Brown under Three Strikes to 25 years to life.
Brown appealed his sentence, arguing that the term imposed was disproportionate to his offense and therefore in violation of the federal and state constitutional prohibitions against cruel and unusual punishment. The California Court of Appeal issued an unpublished opinion affirming Brown’s sentence, and the California Supreme Court denied his petition for review *1024without opinion. Brown filed a habeas petition in the California Court of Appeal and later in the California Supreme Court, but both courts issued bare denials of the petitions.
Brown then petitioned for habeas relief in the federal district court, raising four claims: (1) the Three Strikes law is unevenly applied; (2) he should be resen-tenced pursuant to the California Supreme Court decision of People v. Superior Court (Romero), 13 Cal.4th 497, 53 Cal.Rptr.2d 789, 917 P.2d 628 (1996) (allowing judges to “strike” a defendant’s prior strikes for purposes of applying Three Strikes, if it would be “in furtherance of justice”), decided after he was sentenced; (3) 25 years to life for petty theft constitutes cruel and unusual punishment; and (4) his prior convictions should be stricken because they occurred before Three Strikes was enacted.
The magistrate judge’s report construed the uneven application argument as an equal protection claim and the request to strike the prior convictions because of their timing as an ex post facto claim, and recommended rejecting both contentions on the merits. The report also recommended that the Eighth Amendment claim be rejected on the merits and that the request to be resentenced be denied, because such relief must be pursued in state court. The district court adopted these recommendations in full and denied the habeas petition. After obtaining a COA for all four issues from the district court, Brown raised each of them in his original pro se habeas petition to this court.
3. Prior Proceedings in This Court
Bray and Brown initially filed pro se petitions in this court. After Andrade was decided, we consolidated the cases, appointed counsel, and ordered supplemental briefing and argument regarding the impact of Andrade on the constitutionality of Bray’s and Brown’s sentences.
II. DISCUSSION
We review de novo a district court’s denial of a 28 U.S.C. § 2254 petition. Bribiesca v. Galaza, 215 F.3d 1015, 1018 (9th Cir.2000). Because Bray and Brown filed their federal habeas petitions after April 24, 1996, the amendments to 28 U.S.C. § 2254 under the Antiterrorism and Effective Death Penalty Act of 1996 (AEDPA) apply. Van Tran v. Lindsey, 212 F.3d 1143, 1148 (9th Cir.2000).
Under AEDPA, a federal court may grant a writ of habeas corpus to a state prisoner only if the state court’s rulings “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 were “based on an unreasonable determination of the facts in light of the evidence presented” in the state courts. 28 U.S.C. § 2254(d). A state court decision is “contrary to” clearly established federal law if it “failed to apply the correct controlling authority from the Supreme Court.” Shackleford v. Hubbard, 234 F.3d 1072, 1077 (9th Cir.2000); see also Williams v. Taylor, 529 U.S. 362, 405-07, 120 S.Ct. 1495, 146 L.Ed.2d 389 (2000); Packer v. Hill, 277 F.3d 1092, 2002 WL 47063 (9th Cir. Jan.15, 2002). In order to merit habeas relief under the “contrary to” clause of AEDPA, however, a petitioner must show not only that the state court failed to apply clearly established Supreme Court law but also that it reached an erroneous decision that warrants issuance of the writ under the standard in Brecht v. Abrahamson, 507 U.S. 619, 637, 113 S.Ct. 1710, 123 L.Ed.2d 353 (1993) (requiring that the error have had a substantial or injurious effect on the verdict). See Packer, 277 F.3d at 1102.
*1025The requirements for relief are somewhat higher where the state court applied the clearly established federal law but erred in doing so: A state court’s decision applying clearly established federal law is “unreasonable” under AEDPA only when we are left “with a ‘firm conviction’ that one answer, the one rejected by the [state] court, was correct and the other, the application of the federal law that the [state] court adopted, was erroneous — in other words that clear error occurred.” Van Tran, 212 F.3d at 1153-54. The Brecht standard must be met as well in “unreasonable application” cases. See Packer, 277 F.3d at 1102.
As we develop below, (see Part C, infra ), Bray and Brown are properly characterized as “contrary to” cases because the state court decisions in both cases failed to apply some or all of the required Supreme Court analysis as enunciated in Rummel v. Estelle, 445 U.S. 263, 100 S.Ct. 1133, 63 L.Ed.2d 382 (1980), Solem v. Helm, 463 U.S. 277, 103 S.Ct. 3001, 77 L.Ed.2d 637 (1983), and Harmelin v. Michigan, 501 U.S. 957, 111 S.Ct. 2680, 115 L.Ed.2d 836 (1991). In Andrade, however, we held that the petitioner was entitled to relief because the state court decision involved an “unreasonable application” of Rummel, Solem, and Harmelin. 270 F.3d at 766-67. Because the substantive issues in Bray and Brown are so similar to those we recently resolved in Andrade, and because applying Andrade’s analysis here leads to the conclusion that the state court decisions in Bray and Brown were clearly erroneous, we will analyze the issues here under the more stringent “unreasonable application” standard. As petitioners meet the higher threshold of “clear error” that is required to show an “unreasonable application” of Supreme Court law, a forti-ori they meet the lower requirement of “error” that applies in a “contrary to” law case.
A. The Andrade Opinion
In Andrade, this court held that the California Court of Appeal unreasonably applied clearly established Supreme Court law when it held that a sentence of life without possibility of parole for 50 years for two petty theft convictions did not violate the Eighth Amendment’s prohibition against cruel and unusual punishment. 270 F.3d at 747.
Andrade was convicted of two separate counts of petty theft for shoplifting a total of nine videotapes valued at $153.54 from two different K-mart stores, on occasions two weeks apart. Because he had a prior theft conviction, Andrade was charged with a felony for each of the two petty theft counts. The offenses were tried together (although they need not have been). The resulting petty theft convictions were counted as Andrade’s third and fourth strikes under Three Strikes, as Andrade had at least two prior serious felony convictions — specifically, three prior residential burglary convictions. Three Strikes mandated a sentence of 25 years to life, with no eligibility for parole for at least 25 years, for each petty theft conviction. The judge ordered, pursuant to a Three Strikes provision, § 667(e)(2)(B), that the sentences run consecutively, so Andrade would not be eligible for parole for at least 50 years. 270 F.3d at 746.
After reviewing the relevant Supreme Court law on the Eighth Amendment, An-drade concluded that “three objective criteria ... guide proportionality analysis under the Eighth Amendment: (i) the gravity of the offense and the harshness of the penalty; (ii) the sentences imposed on other criminals in the same jurisdiction; and (iii) the sentences imposed for commission of the same crime in other jurisdictions.” Id. at 756 (quoting Solem, 463 U.S. at 292, 103 S.Ct. 3001). Nevertheless, this court recognized that under “the *1026rale of Harmelin” articulated in Justice Kennedy’s controlling opinion in that case, the “Eighth Amendment does not require strict proportionality between crime and sentence. Rather, it forbids only extreme sentences that are ‘grossly disproportionate’ to the crime.” Id. at 754 (quoting Harmelin, 501 U.S. at 1001, 111 S.Ct. 2680 (Kennedy, J., concurring)). A court, therefore, need not consider the second and third prongs of Solem’s test if the first factor — a comparison of the punishment to the offense — does not raise an inference of gross disproportionality. Id. at 758.
Comparing the sentence in the case before it to those in the most closely analogous Supreme Court Eighth Amendment cases, Andrade found that the penalties in that case — two consecutive life sentences, each without possibility of parole for 25 years — were much harsher penalties than the sentence in Rummel, because Rummel would have been eligible for parole in 12 years or less. Id. at 264, 100 S.Ct. 1133.6 The court analogized the penalty instead to the sentence of life without possibility of parole in Solem.7 Because Andrade would not be eligible for parole until age 87, ten years beyond the life expectancy of a 37 year old male, the court referred to his sentence as “the functional equivalent of ... life in prison without possibility of parole.” Id. at 759.
Recognizing that harsher punishments for recidivists are justified, Andrade stressed that “the enhanced punishment imposed for the [present] offense is not to be viewed as ... [an] additional penalty for the earlier crimes, but instead as a stiffened penalty for the latest crime, which is considered to be an aggravated offense because a repetitive one.” Id. (quoting Witte v. United States, 515 U.S. 389, 400, 115 S.Ct. 2199, 132 L.Ed.2d 351 (1995)). Focusing on the “latest crime,” Andrade concluded that shoplifting nine videotapes was comparable to the offense in Solem of uttering a no-account check. Id. Andrade also noted that the core conduct of petty theft is not conduct traditionally punishable as a felony but as a misdemeanor, punishable by a fine or a jail sentence of six months or less. Id. Since “the core conduct for which Andrade was sentenced is, in the first instance, classified as a misdemeanor rather than a felony,” 270 F.3d at 760, using petty theft with a prior theft conviction, ordinarily punishable by up to three years in prison, §§ 666, 18, to serve as the “third strike” creates a “unique quirk,” allowing a defendant’s recidivism to be “double counted.” Andrade, 270 F.3d at 759-60. Further, noted Andrade, deference to legislative judgments concerning the appropriate “extreme sentences” is less pronounced when the offense is not classified as a felony. Id. at 760; see also Riggs, 525 U.S. at 1114, 119 *1027S.Ct. 890 (Stevens, J., memorandum opinion respecting the denial of the petition for writ of certiorari).
Andrade concluded that the threshold comparison of the harshness of the penalty to the gravity of the crimes led to an inference of gross disproportionality and that Andrade’s criminal record did not “dissipate” that determination. 270 F.3d at 761.
In light of its conclusion that the first Solem factor raised an inference of gross disproportionality, Andrade proceeded to the second factor — whether the sentence is excessive in comparison to sentences imposed on other criminals in California. 270 F.3d at 761. Andrade again noted that petty theft is ordinarily punished by no more than six months in jail, or, if committed after a prior theft conviction, by a term of up to three years in prison (if charged as a felony) or up to one year in jail (if charged as a misdemeanor). See id.; see also § 666, 18. And violent offenses such as second degree murder, voluntary manslaughter, and sexual assault carry much less serious penalties than An-drade’s Three Strikes sentence. 270 F.3d at 761-62.
The State argued in Andrade, as it does here, that the indeterminate life sentence was in line with sentences imposed on other recidivist petty theft offenders under Three Strikes. The court in Andrade was not persuaded by that argument, stating: “Although we agree that comparisons to other sentences for other recidivists are relevant, the problem with the State’s argument is that it attempts to justify the eonstitutionally-suspect application of a statute by pointing to other applications of the same statute. We find this approach less than convincing.” Id. at 762. An-drade concluded that the intrajurisdictional comparison supported the inference that Andrade’s sentence was grossly disproportionate. Id.
Applying the final prong of the Solem analysis, Andrade found only four other jurisdictions where the “triggering offense (petty theft with a prior) could qualify for recidivist sentencing: Rhode Island, West Virginia, Texas, and Louisiana.” Id. at 763. Looking closely at the law in those jurisdictions, Andrade concluded that the Rhode Island recidivism statute applies only to thefts of more than $100; West Virginia does not count non-violent priors; Texas has a liberal parole policy, so the minimum sentence is much less than in California; and, while Louisiana might have, at the time, imposed a comparable sentence to the one Andrade received, there was “a distinct possibility, unlike in California, that a Louisiana court might have invalidated such a sentence as excessive under the state constitution.” Id. at 763-65. The possibility of a comparable sentence in only one other jurisdiction, held Andrade, strengthened rather than undermined the conclusion that the sentence was grossly disproportionate to the crimes. Id. at 765.
Having decided that the California Court of Appeal’s holding was erroneous, Andrade further concluded that the result was contrary to or an unreasonable application of clearly established United States Supreme Court law, entitling Andrade to relief under 28 U.S.C. § 2254. Id. at 766-67. Andrade held that “the law governing the application of the Eighth Amendment to non-violent offenders sentenced to life imprisonment was clearly established” and that a proper proportionality analysis requires a comparison to Rummel, Solem, and Harmelin. Id. at 766. The California Court of Appeal had questioned the validity of Solem after Harmelin and focused its analysis exclusively on Rummel, concluding that Andrade’s sentence was not disproportionate when his crimes and criminal history were compared with that of Rummel. Id. at 766. Andrade held that “the California Court of Appeal’s disregard *1028for Solem results in an unreasonable, application of clearly established Supreme Court law” and that “[i]ts conclusion that Andrade’s sentence does not violate the Eighth Amendment is irreconcilable with the Supreme Court’s decision in Solem and thus constitutes clear error.” Id. at 766-67.
B. Application of Andrade to Bray’s and Brown’ Sentences
Bray’s and Brown’s cases are very similar to Andrade’s in most respects. As in Andrade, Bray and Brown were convicted of shoplifting merchandise worth a small amount of money, an offense ordinarily punishable by a maximum of six months in jail, and sentenced to indeterminate life sentences. While the circumstances of these cases vary in several respects from those in Andrade, we conclude that none of these distinctions justifies a different result.
1. Gross Disproportionality
The State argues that Bray’s and Brown’s sentences are only half as long as Andrade’s, so that Andrade’s gross dis-proportionality analysis has no application here. Andrade, however, was sentenced to 50 years to life for two petty theft convictions; his sentence was nothing more than a 25-year-to-life sentence for a petty theft conviction followed by a consecutive, identical sentence for a second petty theft conviction, imposed for a distinct, albeit similar, offense that occurred at a different time and place. Although Andrade was tried and sentenced at one time for his two offenses, the joint conviction was fortuitous; there could as easily have been separately imposed consecutive sentences. Moreover, Bray’s and Brown’s sentences are not half as long as An-drade’s. Although their minimum term is half as long as Andrade’s minimum term, Bray and Brown were sentenced to indeterminate life sentences and could serve as long for their single petty theft convictions as Andrade will for two.
It bears noting, in this connection, that the standard we are applying is one of proportionality — the relationship of the conviction to the crime. If Andrade’s 50-year-to-life sentence for two petty theft convictions was grossly disproportionate, it follows that a 25-year-to-life sentence is grossly disproportionate to one petty theft conviction. A combined sentence for two entirely separate offenses cannot be grossly disproportionate if each individual sentence is not grossly disproportionate.8
Andrade was sentenced to life imprisonment, with no possibility of parole for 50 years, at which time he would be 87 years old. Bray and Brown will both be eligible for parole in 25 years, when they will be about 59 and 67 years old, respectively. As to these possible differences in age on release, that factor cannot be determinative. An Eighth Amendment analysis necessarily considers the punishment for the offense, Solem, 463 U.S. at 292, 103 S.Ct. 3001, taking into account only those personal circumstances that may mitigate one’s culpability in committing the crime. See, e.g., Penry v. Lynaugh, 492 U.S. 302, 340, 109 S.Ct. 2934, 106 L.Ed.2d 256 (1989). So, while Andrade mentioned the petitioner’s age at possible release, the court could not have meant that the same sentence would have been acceptable for a 19-year old, or that a person with a limited *1029life expectancy is constitutionally entitled to a short sentence for the same crime as a co-defendant not so impaired. Rather, the fact that Andrade could well die before serving out his sentence simply underscored the length of the mandatory sentence. Here, Bray and Brown entered prison as relatively young men and will emerge, if at all, as senior citizens (Brown) or close thereto (Bray), again demonstrating the length of their punishment. See Sistrunk v. Armenakis, 271 F.3d 1174, 1183 (9th Cir.2001) (Kozinski, J., dissenting) (stating that the defendant’s life was at stake, because “to an adult man, a thirty-year sentence pretty much is life”).
2. Intrajurisdictional Comparison
Nor does the length of Bray’s and Brown’s sentences change the result of the intrajurisdictional comparison performed in Andrade. Bray and Brown could each have been sentenced for up to three years in prison under Section 666 for their single petty theft convictions, in light of their prior records, while Andrade could have been sentenced for up to six years for his two petty thefts. A 25-year minimum sentence bears the same relationship to the usual three-year sentence for Bray’s and Brown’s crimes as a 50-year minimum does to the usual six-year sentence. See Andrade, 270 F.3d at 761.
Further, the violent crimes to which An-drade compared the 50-year sentence— second degree murder, voluntary manslaughter, rape, and sexual assault on a minor — all carry sentences considerably less than 25 years to life. See id. at 761-62. Moreover, defendants who commit the same crimes as Brown and Bray and whose records include serious or violent crimes but no theft convictions can be punished under California law by no more than six months in jail. See § 666. So Bray and Brown were sentenced to higher terms than criminals who commit serious violent crimes, and than criminals who commit the same crime and have a comparable past record of violent or serious crime.
Additionally, Andrade must necessarily have based its intrastate comparison on one 25-year-to life sentence rather than two; otherwise, the comparison should have been to two convictions for violent crimes, which it was not. See 270 F.3d at 761-62. Because Bray and Brown received indeterminate life sentences for one petty theft conviction although they could not have been so sentenced for many violent crimes, their sentence, if anything, is more disproportionate on an intrajurisdic-tional basis than was Andrade’s.
Bray’s and Brown’s sentences, we recognize, do not have the distinguishing feature of Andrade’s sentence, which was twice as long as that of most petty theft offenders sentenced under Three Strikes. But again, Andrade was sentenced for two, entirely distinct offenses. Anyone sentenced under Three Strikes for two petty thefts with priors would have received the same sentence. Any lack of similar sentences, then, must have been because no one else was sentenced for two such petty thefts under Three Strikes, not because others who were sentenced for similar crimes received lesser sentences.
The State nonetheless maintains that because a few hundred other defendants have been sentenced to 25 years to life under Three Strikes with the triggering offense of petty theft, the sentence is not disproportionate. As Andrade held, this approach is “less than convincing,” because “it attempts to justify the constitutionally-suspect application of a statute by pointing to other applications of the same statute.” Id. at 762. In other words, that a sentence is imposed frequently, while relevant to proportionality analysis, cannot be the determining factor, as the protections of the Eighth Amendment are not reserved only for aberrant situations. If, for example, *1030the state decided to chop off the hands of everyone convicted of speeding, the likely conclusion that such a sentence is cruel and unusual would not change because the state inflicted it on many people. Thus, while a comparison between a particular defendant’s sentence and that imposed on other recidivists may sometimes be informative, as it was in Andrade, such comparison is neither necessary nor, if one discovers only that others have been similarly sentenced under the same statute, entitled to much weight.
3. Interjurisdictional Comparison
Andrade noted that in only four states can petty theft with a prior qualify for recidivist sentencing. Looking at those four states, we conclude that at the time his offense was committed and at the time he was sentenced, Bray could not have received a life sentence without possibility of parole in any of them. Brown could have received a life sentence without possibility of parole in Louisiana, because he was arrested and sentenced while a version of the Louisiana law so permitting was in effect. But, Louisiana has since amended its habitual offender law so that such a sentence is not currently available in Louisiana in either Bray’s or Brown’s case. Thus, if one can divine a contemporary judgment on the matter among the states, it is that the sentences Brown and Bray received are disproportionate to their petty theft offenses.
a.Rhode Island
Like Andrade, Bray and Brown were convicted of stealing merchandise worth less than $100, an offense that cannot count as a felony in Rhode Island, even with prior theft convictions. R.I. Gen. Laws § 11 — 41—20(d); see also 270 F.3d at 763. Thus, the additional 25-year penalty for three-time felons, R.I. Gen. Laws § 12-19-21, would not have applied to either Bray or Brown, and the maximum term that Rhode Island could have imposed on them would be one year, id. § 11 — 41—20(d).
b.Texas
If two prior theft convictions were counted for each of them, Bray and Brown could have received up to 20 years in prison for a petty theft conviction under Texas’ habitual offender law, Tex. Penal Code Ann. §§ 31.03(e)(4)(D), 12.42(a)(2) & (3), 12.33, but they would have been eligible for parole in five years, or even less with good time credits, Tex. Gov’t Code Ann. § 508.145(f) — a distinctly less onerous sentence than the mandatory 25-year sentence they will have to serve in California.
c.West Virginia
West Virginia allows for a life sentence upon a third felony conviction. W. Va. Code § 61 — 11—18(c). West Virginia, however, provides by statute that offenders sentenced to life under the recidivist statute are eligible for parole in 15 years. Id. § 62-12-13. Even if West Virginia would have allowed a life sentence for Bray or Brown, they would, have been eligible for parole ten years earlier there than in California. Further, while Andrade concluded that West Virginia does not allow life sentences for non-violent recidivists, 270 F.3d at 765, West Virginia also precludes life sentences for some recidivists with violent prior felonies.9
*1031Under West Virginia constitutional proportionality law, the principal offense, not preceding felony convictions, is the central, albeit not exclusive, focus, “since it provides the ultimate nexus to the sentence.” Wanstreet v. Bordenkircher, 166 W.Va. 523, 276 S.E.2d 205, 212 (1981) (holding that a life sentence for check forgery violated the state constitution, even though one of the prior felonies was for arson); see also State v. Miller, 184 W.Va. 462, 400 S.E.2d 897, 898 (1990) (finding life sentence disproportionate for an assault conviction that involved a firearm, with prior felonies of breaking and entering, forgery, and false pretenses); State v. Lewis, 191 W.Va. 635, 447 S.E.2d 570, 575 (1994) (holding that a provision of the criminal code requiring a sentence of one year in prison for a third shoplifting offense violated the state constitutional prohibition against cruel and unusual punishment). Using this approach, the West Virginia Supreme Court has, on at least one occasion, held a life sentence in violation of state proportionality standards when the offender had a violent prior offense, stressing the remoteness in time of the violent offense. State v. Deal, 178 W.Va. 142, 358 S.E.2d 226, 231 (1987) (finding a life sentence disproportionate for possession of a controlled substance where the record revealed a violent prior felony conviction 16 years earlier).
Three of Bray’s violent felony convictions occurred 15 years earlier, while the other was eight years before. It is therefore possible that, focusing on the nonviolent nature of bis petty theft offense and acknowledging that his prior violent felony convictions were dated, Bray’s sentence would have been considered excessive in West Virginia. Brown’s prior violent felony convictions occurred 13, 19, and 24 years prior to his petty theft offense. His sentence might well have been considered excessive in West Virginia, based on the age of the violent offenses.
d. Louisiana
Finally, under Louisiana’s habitual offender statute, at the time the last offenses in these cases were committed, Bray could not have received a comparable sentence, although Brown could have received a higher one.
i. Bray
Before August 15, 1995,10 the Louisiana habitual offender statute required that both the third or fourth strike triggering life imprisonment and two of the prior felonies be “a crime of violence ..., a sex offense, or ... a violation of the Uniformed Controlled Substances Law punishable by imprisonment for ten years or more or any other crime[ ] punishable by imprisonment for twelve years or more.” See 1995 La. Sess. Law. Serv. 1245 § 1 (West) (amending La.Rev.Stat. Ann. § 15:529.1(A)(l)(b)(ii) & (c)(ii)). Because his current offense, albeit treatable as a felony if two prior thefts were considered, see La.Rev.Stat. Ann. § 14:67(B)(3), is not within any of these special categories of felonies, Bray could not have received such a sentence had he committed his offense in Louisiana at the time he committed his petty theft in California.
Rather, the applicable Louisiana law when Bray committed his offense and received his sentence would have allowed him to be sentenced to a maximum of four years for his current offense: That offense could only have been charged as a third felony in Louisiana, because Louisiana considers only offenses tried separately. *1032Bray was convicted of three of his four robberies in one trial, so he had — and has — at most three strikes under Louisiana law. See Andrade, 270 F.3d at 764 n. 22, 765 (citing State v. Butler, 601 So.2d 649, 650 (La.1992); State v. Corry, 610 So.2d 142, 147 (La.Ct.App.1992)). The petty theft offense, with two prior theft offenses, could be treated as a second or third subsequent felony, in which case the maximum sentence for Bray would have been twice the two-year maximum for a first-time offender. La.Rev.Stat. Ann. §§ 14:67(B)(3), 15:529(A)(1)(b)(i); see also Andrade, 270 F.3d at 764 n. 22.
Louisiana has recently amended its habitual offender law so that it currently reads as it did before August of 1995. 2001 La. Sess. Law Serv. 403 (West). For a period of about six years, however, including the time at which his court of appeal decision was issued, Louisiana could have imposed a sentence of life without possibility of parole on Bray. See La. Rev.Stat. Ann. §§ 14:67(B)(3), 15:529.1(A)(1)(b)(ii) & (e)(i)-(ii) (West 2000), amended by 2001 La. Sess. Law Serv. 403 (West); see also Andrade, 270 F.3d at 765 & n. 22.11 As the statute so providing was not in effect when Bray committed his last offense and is not in effect now, however, it is of no relevance to the interjurisdictional comparison.
ii. Brown
Brown committed his offense and received his sentence while the harsher, interim version of Louisiana’s habitual offender law was in effect.12 He therefore could have received a sentence of life without parole had he committed his petty theft offense in Louisiana on the same date that he committed it in California. Brown’s two prior strikes — -assault with a deadly weapon and robbery — -would have been considered crimes of violence in Louisiana, so Brown would have been subject to a sentence of life without possibility of parole under the Louisiana statutes in effect during this interim period. See La. Rev.Stat. Ann. § 15:529.1(A)(l)(b)(ii) & (c)(ii) (West 2000), amended by 2001 La. Sess. Law Serv. 403. It appears, however, that, even while this version of the statute was in effect, a life sentence without possibility of parole for petty theft might well have been vulnerable to successful challenge under the Louisiana Constitution, despite Brown’s violent priors, given other recent Louisiana proportionality decisions. See Andrade, 270 F.3d at 765 (citing State v. Hayes, 739 So.2d 301, 303-04 (La.App.1999) (holding that a life sentence was impermissibly excessive for a defendant convicted of theft of over $1000 who had a prior robbery conviction, considered violent in Louisiana); State v. Burns, 723 So.2d 1013 (La.Ct.App.1998)); see also State v. Neal, 762 So.2d 281, 286 (La.Ct.App.2000) (finding a mandatory life sentence without possibility of parole under the habitual offender statute to be unconstitutionally excessive where the defendant’s current offense was theft of $160 worth of goods and his priors included two *1033violent offenses — attempted manslaughter and aggravated battery).
Under the recent amendments to Louisiana’s habitual offender statute, Brown could not be subject to a mandatory life sentence without possibility of parole, but he could receive a minimum sentence of 20 years for his last offense — a fourth or subsequent felony — had his entire record been proven to the trier of fact. See La.Rev. Stat. Ann. § 15:529.1(A)(l)(c)(i).13 This sentence would be less onerous than his Three Strikes sentence in California: The sentence would be five years shorter, and it is possible that Brown would be eligible for parole before he served 20 years.14
To summarize: Under both the law in effect at the time of his offense and current Louisiana law, Bray would have received a much lower sentence in Louisiana than in California. While Brown could have received a higher sentence in Louisiana originally, he would now receive a lower sentence in Louisiana than in California, and might be eligible for parole. So, there was at most one jurisdiction that *1034conceivably would have imposed a higher sentence on one of these defendants, and that jurisdiction has since concluded — -in an era when legislatures are hardly prone to impose light sentences on repeat criminals — that such a sentence is too high, and would now impose a lower sentence than in California.
Recent rejection of a higher sentence by the only state that perhaps would have allowed it in narrow circumstances signals a considered national legislative judgment based on actual experience that California’s sentence is indeed disproportionate to the crime. See Estelle v. Gamble, 429 U.S. 97, 102, 97 S.Ct. 285, 50 L.Ed.2d 251 (1976) (“[W]e have held repugnant to the Eighth Amendment punishments which are incompatible with ‘the evolving standards of decency that mark the progress of a maturing society’.”) (quoting Trop v. Dulles, 356 U.S. 86, 101, 78 S.Ct. 590, 2 L.Ed.2d 630 (1958) (plurality opinion)). “[T]he circumstance that a State has the most severe punishment for a particular crime does not by itself render the punishment grossly disproportionate,” Harmelin, 501 U.S. at 1000, 111 S.Ct. 2680, and the interjurisdic-tional comparison cannot in any event be the determining factor in an Eighth Amendment analysis.15 Nonetheless, the fact that California is comparatively isolated in its judgment concerning the appropriate punishment for petty theft by a recidivist, even for a recidivist with some violent criminal history, “ ‘validate[s][the] initial judgment that [the] sentence is grossly disproportionate to [the] crime’.” Andrade, 270 F.3d at 765 (quoting Harmelin, 501 U.S. at 1005, 111 S.Ct. 2680).
4. Significance of Violent Prior Offenses
The final possible point of distinction between these cases and Andrade is that both Bray’s and Brown’s past criminal record includes crimes classified by California as violent crimes, while Andrade’s did not. See § 667.5. For several reasons, this distinction cannot serve to justify a different result than in Andrade.
First, this asserted difference is somewhat ephemeral. Andrade’s prior convictions could be considered objectively violent, while it does not appear that any of Bray’s or most of Brown’s priors were considered “violent” under California law at the time of conviction.
Andrade classified Andrade’s residential burglary prior convictions as non-violent, as they are not in the list of violent offenses, § 667.5, referenced by Three Strikes. Nevertheless, residential burglary carries a strong potential for violence and is treated as a violent crime for other purposes, including under federal law. See Taylor v. United States, 495 U.S. 575, 581, 588, 110 S.Ct. 2143, 109 L.Ed.2d 607 (1990) (noting that the legislative history of the Armed Career Criminal Act of 1984 indicates that burglary was included because it is one “of the most violent street crimes,” and “because of its inherent potential for harm to persons” and that “Congress apparently thought that all burglaries serious enough to be punishable by imprisonment for more than a year constituted a category of crimes that shared this potential for violence ... ”).16
Conversely, California law did not categorize ordinary robbery as “violent” when *1035Bray and Brown were convicted. Although Three Strikes references a section listing violent offenses that currently includes “any robbery,” § 667.5(c)(9), this section was only recently amended to include all robberies, Prop. 21 § 15 (approved March 7, 2000). When Bray and Brown were sentenced, section 667.5 included only robberies perpetrated in a dwelling house or inhabited building or trailer where either (1) “it is charged and proved that the defendant personally used a deadly or dangerous weapon,” § 667.5(c)(9) (West 1999), amended by Prop. 21 § 15 (approved March 7, 2000); or (2) the defendant voluntarily acted in concert with two or more other persons, § 667.5(e)(18) (West 1999), amended by Prop. 21 § 15 (approved March 7, 2000); see also § 213(a)(1)(A). Crimes of violence, as defined by section 667.5, also included any felony in which the defendant inflicts great bodily injury on any person or in which the defendant uses a firearm. § 667.5(c)(8).
It is unlikely that any of Bray’s four robbery convictions would have been classified as violent under section 667.5. The first two convictions took place in a ear and the third outside on railroad tracks. Nor did Bray himself use a firearm or inflict great bodily injury on any person. The record does not reveal facts indicating that the fourth robbery conviction would have fallen within section 667.5 at the time of Bray’s appeal.
One of Brown’s prior strikes — the assault with a deadly weapon, which involved a firearm — would have been classified as violent under this statute. The record does not reveal any facts of Brown’s robbery conviction, other than that it was originally a conviction for burglary, so we cannot assume that it would have met the requirements of a violent felony robbery.
Second, the presence of violent prior offenses might well be of great significance were the crime of conviction a violent crime, but cannot be where the crime of conviction is non-violent. Where the crime of conviction is a violent one, a more severe recidivist sentencing scheme for defendants with past convictions for violent crimes would simply reflect a judgment that such individuals cannot curb their violence and should therefore be imprisoned for at least a lengthy time and for as long as life. But where, as here, the present conviction does not demonstrate continued proclivity toward involvement in violent crime, distinguishing between criminals convicted for non-violent offenses on the basis of their past violence would run up against compelling Double Jeopardy Clause considerations.
Recidivist sentencing schemes, imposing higher sentences on repeat offenders, have long been held constitutional in the face of Double Jeopardy challenges. As an early case put it, summarizing and quoting from still-earlier decisions, legislators may constitutionally conclude that “ ‘one ,who proves, by a second or third conviction, that the former punishment has been inef-ficacious in doing the work of reform for which it was designed’ ‘has evidenced a depravity, which merits a greater punishment, and needs to be restrained by severer penalties than if it were his first of-*1036fence.’ ” Moore v. Missouri, 159 U.S. 673, 677, 16 S.Ct. 179, 40 L.Ed. 301 (1895), quoting Plumbly v. Commonwealth, 43 Mass. (2 Met.) 413, 1841 WL 3384 (1841), and People v. Stanley, 47 Cal. 113, 1873 WL 1267 (1873); see also, e.g., Nichols v. United States, 511 U.S. 738, 747, 114 S.Ct. 1921, 128 L.Ed.2d 745 (1994); Spencer v. Texas, 385 U.S. 554, 559-60, 87 S.Ct. 648, 17 L.Ed.2d 606 (1967); Gryger v. Burke, 334 U.S. 728, 732, 68 S.Ct. 1256, 92 L.Ed. 1683 (1947) (“The sentence as a fourth offender or habitual criminal is not to be viewed as either a new jeopardy or additional penalty for the earlier crimes.- It is a stiffened penalty for the crime, which is considered to be an aggravated offense because a repetitive one.”)
At the same time, “[t]he Constitution was designed as much to prevent the criminal from being twice punished for the same offense as from being twice tried for it.” Ex parte Lange, 85 U.S. (18 Wall.) 163, 173, 21 L.Ed. 872 (1874); see also Witte, 515 U.S. at 395-96, 115 S.Ct. 2199. It is for this reason that the Supreme Court has repeatedly stressed, in upholding recidivist sentencing schemes, that the priors can be relevant only as they aggravate the defendant’s culpability for the crime of conviction. If that connection between the prior convictions and the present one is lost, then the Double Jeopardy concerns reemerge. See Riggs, 525 U.S. at 1114, 119 S.Ct. 890 (Stevens, J., memorandum opinion respecting the denial of the petition for writ of certiorari).
In this connection, one can perceive two possible theories upon which a recidivist statute can maintain the relationship between the current crime and past convie-tions so as to avoid Double Jeopardy concerns about imposing a new punishment for past offenses: A harsher sentence for a new crime can be warranted either (1) because the defendant’s repeated violations of the criminal law reveal his incapability of conforming to society’s norms in general, see Rummel, 445 U.S. at 276, 100 S.Ct. 1133 (“The interest in recidivist statutes is in dealing in a harsher manner with those who by repeated criminal acts have shown that they are simply incapable of conforming to the norms of society as established by its criminal law”); or (2) because the defendant’s current offense involves repetition of a particular offense characteristic, indicating that the defendant remains prone to that specific kind of antisocial activity — as for example, when a defendant commits a second theft offense, demonstrating proclivity toward stealing. If neither of these theories serves to justify the sentencing enhancement for the principal offense, then it is hard to escape the conclusion that the enhancement is simply an additional punishment for the previous offenses, in violation of the Double Jeopardy Clause.
Andrade’s holding forecloses application of the first theory — that a general lawbreaking. tendency can justify Three Strikes’ mandatory indeterminate life sentence for petty theft. See 270 F.3d at 747. After Andrade, for all the reasons already surveyed, an indeterminate life sentence for a defendant convicted of felony petty theft with a prior who has at least two prior serious felony convictions, see § 1192.7, violates the Eighth Amendment’s prohibition against cruel and unusual punishment.17
*1037If we attempt to distinguish Andrade solely on the basis that Bray and Brown have prior felonies that may have been violent, as opposed to serious, then we would be punishing Bray and Brown as non-violent lawbreakers who were violent in the past. This practice could not be justified under the second, particular criminal proclivity approach. Rather, the sentence would necessarily be “an additional penalty for their earlier [violent] crimes,” for which Bray and Brown have already been punished. See Gryger, 334 U.S. at 732, 68 S.Ct. 1256; Solem, 463 U.S. at 297 n. 21, 103 S.Ct. 3001; Riggs, 525 U.S. at 1114, 119 S.Ct. 890 (Stevens, J, memorandum opinion respecting the denial of the petition for writ of certiorari). Because such additional penalties for past crimes violate the Double Jeopardy Clause, the prior violence in Bray’s and Brown’s criminal record cannot be a basis for distinction between these cases and Andrade’s.
We note, further, that Three Strikes itself does not distinguish between serious and violent prior offenses. Rather, Three Strikes references other sections of the California Penal Code, which exist for other purposes, to define what felonies count as prior strikes. § 667.5(d)(1) (referring to §§ 667.5(c) and 1192.7(c)). Although certain of these offenses can be found in Section 667.5(c) and are labeled as violent, while other strikes appear only in Section 1192.7(c) and are labeled as serious, the category into which prior convictions fit has absolutely no bearing on the application or length of a Three Strikes sentence. In addition, under the petty theft with a prior statute, violent prior felonies are irrelevant to the enhancement of the petty theft into a felony unless they are also theft crimes. These aspects of the California scheme indicate that California is not enhancing sentences because the prior convictions were for violent crimes. Again, (see n. 18, supra), it makes little sense to defer to a penal judgment that the legislature did not make in determining whether or not a particular sentence is unconstitutionally disproportionate to the crime of conviction.
In sum, these cases are materially indistinguishable from Andrade. We therefore conclude that Bray’s and Brown’s sentences did violate the Eighth Amendment’s prohibition against cruel and unusual punishment.
C. Analysis of the California Courts of Appeal Decisions
In order to merit habeas relief, the California Courts of Appeal decisions 18 must be either contrary to or involve an unreasonable application of clearly established Supreme Court law. Andrade concluded that the United States Supreme Court law governing the Eighth Amendment’s prohibition against cruel and unusual punishment was clearly established at the time of the California Court of Appeal decision in that case, that is on May 13,1997. See 270 F.3d at 766; see also Riggs, 525 U.S. at 1114, 119 S.Ct. 890 (Stevens. J., memorandum opinion respecting the denial of the petition for writ of certiorari) (stating *1038that petitioner sentenced to 25 years to life for petty theft could seek federal habeas relief, because he was asking the Supreme Court to “apply a settled rule of Eighth Amendment law”). Bray’s court of appeal decision was filed on May 21, 1997. Although the court of appeal issued Brown’s decision in 1996, Andrade did not rely on any Supreme Court cases issued after 1991. Therefore, under Andrade, the relevant Supreme Court cases were clearly established law by the time of the California Courts of Appeal decisions in these cases.
If we focus particularly on the fact that Bray and Brown had violent prior convictions, that conclusion does not change. Several Supreme Court cases decided before the California decisions in these cases stated that using sentencing enhancements as an “additional penalty for the earlier crimes” as opposed to a “stiffened penalty for the latest crime” could violate the Double Jeopardy Clause. Witte, 515 U.S. at 400, 115 S.Ct. 2199; see also Solem, 463 U.S. at 297 n. 21, 103 S.Ct. 3001; Gryger, 334 U.S. at 732, 68 S.Ct. 1256; Moore, 159 U.S. at 677, 16 S.Ct. 179; Ex parte Lange, 85 U.S. (18 Wall.) at 173. Thus, the principles that we apply in analyzing the California Courts of Appeal decisions have been clearly established by the United States Supreme Court.
1. California Court of Appeal Opinion in Bray
Bray explicitly raised the argument that his sentence violated the United States Constitution’s prohibition against cruel and unusual punishment. The California Court of Appeal opinion in his case, however, referred exclusively to California law and failed to mention any of the three critical Supreme Court cases. More significantly, the court refused to give any weight to the relatively minor nature of his current offense. After reviewing Bray’s criminal history, the court stated that, “[q]uite clearly, Bray’s sentence is the result of his recidivist behavior and it is that behavior that justifies the 25 years to life term.”19
In Andrade, we held that upholding an indeterminate life sentence for a petty theft offense which is normally a misdemeanor constituted an unreasonable application of clearly established Supreme Court law governing the prohibition against cruel and unusual punishment. 270 F.3d at 766. Because, as we have shown, Bray’s case is materially indistinguishable from Andrade, had the state court conducted an analysis under the controlling precedents, it would have been unreasonable for it not to conclude under the Solem test that Bray’s sentence was grossly disproportionate to his petty theft offense, in violation of the Eighth Amendment. Consequently, the Bray court’s decision that the statute, as applied, was constitutional is clearly erroneous, and Bray would be entitled to relief under the “unreasonable application” clause of AED-PA had the state court applied the relevant Supreme Court precedent. Van Tran, 212 F.3d at 1153-54.20 Having de*1039termined that there was clear error sufficient to satisfy the “unreasonable application” clause, we hold that a fortiori the state court decision was “erroneous” and merits habeas relief under the “contrary to” clause. See Packer, 277 F.Bd at 1102 & n. 12 (holding that, when a state court decision fails to apply controlling Supreme Court precedent, “the fact that the result is erroneous is sufficient, so long as the Brecht standard is met”). Therefore, Bray is entitled to habeas relief.
2. California Court of Appeal Opinion in Brown
The California Court of Appeal’s opinion in Brown, like the opinion in Bray, focused primarily on state law and concluded that Brown’s sentence was not disproportionate to the petty theft offense within the meaning of the California Constitution. Although the Brown court did refer to the Supreme Court’s decision in Harmelin, the court did not apply the controlling Supreme Court test for determining whether a sentence violates the Eighth Amendment. Rather than considering whether Brown’s sentence was grossly disproportionate to the crime of petty theft for which he was convicted, as Solem and Harmelin require, the Brown court compared Brown’s sentence to his entire criminal history, noting that, if life without parole for one drug offense in Harmelin was not disproportionate, then “a fortiori a term of 25 years to life for a person with [Brown’s] record cannot be considered disproportional.” See People v. Brown, C023139, at 3 (Cal.Ct.App.1997) (second emphasis added). Because the addition, deletion, or alteration of a factor in a test established by the Supreme Court constitutes a failure to apply controlling Supreme Court law, Brown’s habeas petition, like Bray’s, is properly resolved under the “contrary to” clause of AEDPA. See Williams, 529 U.S. at 405-06, 120 S.Ct. 1495; Packer, 277 F.3d at 1100-01.
In any event, because we hold that Brown’s case, like Bray’s, is materially indistinguishable from Andrade, the Brown court’s decision that the statute was constitutional as applied was clearly erroneous and would merit habeas relief under the “unreasonable application” clause of AED-PA had the Brown court applied the relevant Supreme Court precedent. See An-drade, 270 F.3d at 766 (holding that the state court’s disregard for Harmelin’s distinguishing of the severity of the defendant’s crime in that case from the “relatively minor” nature of the offenses in Solem resulted in an unreasonable application of clearly established Supreme Court law). The California Court of Appeal itself characterized Brown’s petty theft as a “fairly nonserious offense,” so the court’s application of Harmelin to the facts in Brown was objectively unreasonable. See id. As we explained in our analysis of the state court decision in Bray, the clear error required to satisfy the “unreasonable application” clause of AEDPA a fortiori satisfies the lesser requirement of “error” under the “contrary to” clause. See Packer, 277 F.3d at 1102 & n. 12. Therefore, Brown, like Bray, is entitled to habeas relief under 28 U.S.C. § 2254.21
III. BROWN’S OTHER CLAIMS
A. Uneven Application of the Three Strikes Law
Brown did not make out a prima facie case that the Three Strikes law is unevenly applied in violation of the Equal Protection Clause. Rather, Brown cited *1040only one other case, with facts distinguishable from those in his case. The district court properly found that Brown failed to meet his burden on this claim. See McQueavy v. Blodgett, 924 F.2d 829, 834-35 (9th Cir.1991). We therefore affirm the denial of the habeas petition on this issue.
B. Resentencing Pursuant to Romero
Brown argued that he should be resentenced in light of the California Supreme Court’s decision in Romero, 13 Cal.4th 497, 53 Cal.Rptr.2d 789, 917 P.2d 628, which held that judges have discretion not to count prior qualifying offenses as strikes. The district court correctly concluded that this state law claim is not cognizable on federal habeas review. See Williams v. Borg, 139 F.3d at 740. We affirm the denial of habeas relief with respect to this claim.
C. Ex Post Facto
Brown contends that it is unconstitutional to count as strikes offenses committed prior to Three Strikes’ enactment. The application of a sentencing enhancement due to a prior conviction does not violate the Ex Post Facto Clause, United States v. Sorenson, 914 F.2d 173, 174 (9th Cir.1990), as long as the statute was in effect before the triggering offense was committed, United States v. Ahumada-Avalos, 875 F.2d 681, 683-84 (9th Cir.1984). Three Strikes took effect in March of 1994, before Brown committed the principal offense in August of 1995. We therefore affirm the denial of habeas relief for this claim.
IV. CONCLUSION
We conclude that sentences of 25 years to life for Bray’s and Brown’s petty theft offenses violate the Eighth Amendment’s prohibition against cruel and unusual punishment. Our decision does not hold the California Three Strikes Law unconstitutional, only its application to mandate a 25-year-to-life sentence for a petty theft offense such as those in these cases. Bray and Brown’s sentences of life imprisonment with no possibility of parole for 25 years are grossly disproportionate to their respective crimes- — -stealing three videotapes and a steering wheel alarm — even in light of their criminal records. The California Courts of Appeal decisions upholding their sentences were both contrary to and unreasonable applications of clearly established Supreme Court law.
We therefore REVERSE the district courts’ orders denying habeas relief on this ground, and we REMAND with instructions to issue writs of habeas corpus if, within 60 days following the issuance of our mandate, California has not resen-tenced Bray and Brown in light of our opinion. With respect to Brown’s other claims, we AFFIRM the district court.
. Bray’s criminal record also includes other convictions not considered by the jury — obstructing/resisting a public officer and trespass in 1979, possession of a dangerous weapon in 1985, being under the influence of a controlled substance in 1991, and petty theft with a prior while he was out on bail for the instant offense in 1995.
. Bray's original pro se brief to this court challenged his sentence on a second ground— that the Three Strikes law changed the role of judges and prosecutors and thus was not a proper subject of urgency legislation (legislation that takes immediate effect as opposed to waiting until January 1st at least 90 days after enactment) under the California Constitution. The second issue was not alleged in the district court petition and was not covered by the COA, so we do not have jurisdiction to decide it. In any event, this issue rests solely on state law, so it is not cognizable in a federal habeas proceeding. Williams v. Borg, 139 F.3d 737, 740 (9th Cir.1998).
. The state asserts without citation in its supplemental brief that Brown physically resisted after the store’s security guard caught him, so that his principal offense involved violence. The crime of which Brown was convicted (petty theft with a prior) does not, however, require any proof of violence. Even if violence of which a defendant was not convicted were relevant under the Eighth Amendment— which we do not believe it is — nothing in the record, including the information, the probation officer’s description of the offense, the California Court of Appeal opinion, and the district court opinion, indicates that resistance or violence was involved in the petty theft offense.
. Brown's other convictions include: (1) a misdemeanor conviction in 1986 for being under the influence of a controlled substance; (2) misdemeanor convictions in 1987 for giving false information to the police, driving with a suspended license, and DUI; (3) a 1989 misdemeanor theft conviction; (4) a felony vehicle theft conviction in 1990; (5) misdemeanor convictions in 1990 for giving false information to the police, burglary, and distribution of hypodermic needles without a license; (6) misdemeanor convictions in 1991 for theft, battery, and petty theft with a prior; (7) misdemeanor convictions in 1992 for second-degree robbery and possession of drug paraphernalia; and (8) a misdemeanor conviction in 1994 for possession of controlled substances without a license.
.Brown was originally convicted of felony burglary, § 459, in 1982, but after the conviction was reversed and remanded, pleaded guilty in 1984 to one count of felony robbery.
. In Rummel, the Court upheld a sentence of life imprisonment with possibility of parole for a three-time non-violent felony recidivist. 445 U.S. at 264, 100 S.Ct. 1133. Rummel was convicted of obtaining money by false pretenses, a felony ordinarily punishable by two to ten years in prison. Rummel had two prior felony convictions. Id.
. In Solem, the Court reversed a sentence of life imprisonment without possibility of parole for a seven-time non-violent felony recidivist who was convicted of writing a no-account check. 463 U.S. 277, 103 S.Ct. 3001, 77 L.Ed.2d 637. Helm had six prior felonies, including false pretenses, grand larceny, driving while intoxicated, and three burglary convictions. Id. at 279-80, 103 S.Ct. 3001. Uttering a no-account check was a felony ordinarily punishable by up to five years in prison, but under the recidivist statute Helm was sentenced to life without possibility of parole. Id. at 281, 103 S.Ct. 3001. The Court found Helm's sentence "far more severe than the life sentence we considered in Rummel " because Rummel could be paroled after 12 years, whereas Helm had no possibility of parole. Id. at 297, 100 S.Ct. 1133.
. Justice Stevens and the three other justices who joined his reasoning in Riggs were very concerned about a 25-year-to-life sentence for petty theft, which they analogized to the offense in Solem of writing a bad check. 525 U.S. at 1114, 119 S.Ct. 890 (Stevens, J., memorandum respecting the denial of the petition for certiorari) (noting that the petition "raise[d] a serious question concerning the application of California’s 'three strikes' law”).
. The applicable statutes in West Virginia do not distinguish between violent and non-violent prior felony convictions. See W. Va.Code § 61 — 11—18(c). The West Virginia courts, however, conduct detailed proportionality analysis and, as the cases alluded to in the text indicate, not infrequently hold recidivist sentences invalid after conducting that analysis.
. Bray committed his petty theft on March 28, 1994, and the court sentenced him on April 5, 1995.
. For a third or fourth felony offender whose principal offense was non-violent, the Louisiana habitual offender statute, between 1995 and 2001, distinguished between violent and non-violent prior offenses, providing harsher penalties for offenders with violent priors. La.Rev.Stat. Ann. § 15:529.1 (A) (1) (b)(i) - (ii) & (c)(i)-(ii) (West 2000), amended by 2001 La. Sess. Law Serv. 403. Because at least one of his prior offenses was violent, under the Louisiana statutes Bray could have been sentenced to life without possibility of parole. Id. § 15:529.l(A)(l)(b)(ii), amended by 2001 La. Sess. Law Serv. 403; see also id. § 14:2(13)(w),(y), & (z) (defining armed robbery, simple robbery, and purse snatching as crimes of violence).
. Brown committed the petty theft on August 27, 1995, shortly after the amended Louisiana statute went into effect, and the court sentenced him in 1996.
. Unlike Bray's, Brown’s prior felony convictions occurred on at least three separate occasions.
. It is not entirely clear whether or not parole would be available under Louisiana Law. Although some provisions of the habitual offender statute require the sentence be "without benefit of parole,” the pertinent provision does not mandate parole ineligibility. Compare La.Rev.Stat. Ann. § 15:529.1 (A) (1) (c) (i) (ii) with id. § 15:529.l(A)(l)(C)(i). If the applicable provision of the Louisiana habitual offender statute does not place any restrictions on parole eligibility, then it incorporates the parole restrictions imposed on habitual offenders in the statute covering the crime of conviction. State v. Tate, 747 So.2d 519, 520 (La.1999). Brown would have been convicted under the theft statute, La.Rev.Stat. Ann. § 14:67(B)(3), which includes no restrictions on eligibility for parole. Louisiana cases indicate that under these circumstances, an offender convicted under the habitual offender statute may not be sentenced to a prison term without benefit of parole. See State v. Girod, 703 So.2d 771, 777 (La.Ct.App.1997) (finding that La.Rev.Stat. § 15:529.1(A)(1)(c)(i) "was applicable and it provided for a sentencing range of 20 years to life imprisonment with parole eligibility”); State v. McCadney, 761 So.2d 579, 584 & n. 3 (La.Ct.App.2000) (noting that a defendant sentenced to forty years as a fourth-felony habitual offender was not sentenced without benefit of parole).
Louisiana's general parole provision, however, denies parole eligibility to a third or subsequent felony offender, see id. § 15:574.1(A)(1). The Louisiana courts have explained that where neither the habitual offender statute provision nor the underlying conviction statute restrict parole, the trial court lacks authority to prohibit parole eligibility pursuant to that statute, even where the defendant is ineligible for parole as a third or fourth felony offender under La.Rev.Stat. § 15:574.4(A)(1). See St. Amant v. 19th Jud. Dist. Ct., 678 So.2d 536 (La.1996) (holding that when the statute of conviction does not restrict parole, the trial court must sentence defendant to a term without a prohibition on parole, because "parole eligibility is to be determined by the Department of Corrections pursuant to La.Rev.Stat. § 15:574.4”); State v. Larrivere, 733 So.2d 703, 705 (La.Ct.App.1999) (holding that defendant — a fourth felony offender, and thus ineligible for parole under La.Rev.Stat. § 15:574.4(A)(1) — should have been sentenced without benefit of parole for only the first year of his sentence, as provided by the underlying statute of conviction); State v. Miller, 703 So.2d 698 (La.Ct.App.1997) (finding that the trial court should not have prohibited parole for a third-felony offender, because although La.Rev.Stat. § 15:574.4 prohibited his parole, parole eligibility is to be determined by the Department of Public Safety and Corrections, not by the trial court); State v. Langlois, 620 So.2d 1193, 1195 (La.Ct.App.1993) (finding that the trial court should not have prohibited parole for a fourth-felony offender).
Thus, a Louisiana court could not have imposed the mandatory 20-year sentence without benefit of parole. Precisely how the Department of Corrections, which makes parole eligibility determinations, applies § 15:574.4 is a matter we cannot determine from the case law.
. See Harmelin, 501 U.S. at 1004, 111 S.Ct. 2680 ("Although Solem considered these comparative factors after analyzing the gravity of the offense and the harshness of the penalty, it did not announce a rigid three-part test.”) (internal citation and quotation marks omitted); see also Solem v. Helm, 463 U.S. at 291, 103 S.Ct. 3001 (in determining unconstitutional disproportionality, "no one factor will be dispositive in a given case”); Robinson v. California, 370 U.S. 660, 672, 52 S.Ct. 1417, 8 L.Ed.2d 758 (1962) (holding that a 90 day jail sentence for being a drug addict is cruel and unusual punishment, even though at least a few other jurisdictions had similar statutes).
. In Louisiana, burglary can be a violent crime. See La.Rev.Stat. Ann. § 14:2(13)(v) *1035(listing aggravated burglary as a violent crime in Louisiana). In West Virginia, burglary may also be considered a violent crime. State v. Housden, 184 W.Va. 171, 399 S.E.2d 882, 886 (1990) (burglary is a crime that “by [its] very nature involve[s] the threat of harm or violence to innocent persons”); but see State v. Hedrick, 182 W.Va. 701, 391 S.E.2d 614, 622 (1990) (classifying night-time burglary as a non-violent offense, because "breaking and entering is not per se a crime of violence" and there was "nothing in the record to indicate that weapons were used in these crimes or that there was a threat of violence to any person”).
. Andrade had served only one prison term for his three felony convictions, whereas Bray and Brown each served at least two prison terms. This circumstance, however, does not distinguish their cases from Andrade. Although repeated separate prison terms may suggest that an individual is not deterred from additional crimes by serving time in prison, see Rummel, 445 U.S. at 277, 100 S.Ct. 1133, the California Legislature made no such distinction in Three Strikes. See § 667; see also People v. Benson, 18 Cal.4th *103724, 74 Cal.Rptr.2d 294, 954 P.2d 557, 558 (1998) (holding that although defendant’s two prior felony convictions — residential burglary and assault with intent to commit murder— were sustained in one action and arose out of the same set of facts, they constituted two separate strikes). In analyzing a sentence, we should not defer to distinctions that the State never made in the statute imposing the sentence.
. Because the California Supreme Court denied petitioners’ review petitions without comment, the last reasoned decision on this issue in each case is the opinion by the state court of appeal. Ylst v. Nunnemaker, 501 U.S. 797, 803-04, 111 S.Ct. 2590, 115 L.Ed.2d 706 (1991).
. The standard applied to determine if a sentence violates the California Constitution is different from a "grossly disproportionate” standard. Under California law, the standard is whether the penalty "is so disproportionate to the crime for which it is inflicted that it shocks the conscience and offends fundamental notions of human dignity.” In re Lynch, 8 Cal.3d 410, 105 Cal.Rptr. 217, 503 P.2d 921, 930 (1972). Although the state court’s analysis under California standards is therefore "arguably irrelevant for our purposes,” Andrade, 270 F.3d at 767 n. 24, it is the only indication we have of the state court's reasoning, so we pay it some attention.
. Because the error affected the length of the sentence, it clearly had a substantial and injurious effect. See Brecht, 507 U.S. at 637, 113 S.Ct. 1710.
. The Brecht standard is met in Brown, as in Bray, for the reason explained in footnote 20, supra.