SHAW, Judge.

William A. Barr appeals the circuit court's summary denial of his Rule 32, Ala.R.Crim.P., petition for postconviction relief, in which he attacked his October 7, 2001, conviction for intentional murder and his resulting sentence of life imprisonment without the possibility of parole. This Court affirmed Barr's conviction and sentence on direct appeal in an unpublished memorandum issued on October 18, 2002. See Barr v. State (No. CR-01-0615), 876 So.2d 540 (Ala.Crim.App. 2002) (table). This Court issued a certificate of judgment on November 5, 2002.

Barr filed his Rule 32 petition on December 25, 2005. In his petition, Banalleged that his sentence exceeded the maximum allowed by law because, he said, two of the prior convictions used to enhance his sentence under the Habitual Felony Offender Act ("the HFOA") had been set aside. Specifically, Barr argued that he had been sentenced as a habitual felony offender, but that approximately four years after his sentence was imposed, two of the prior convictions used for enhancement — two convictions for robbery in the second degree — had been set aside. The State filed a response and motion to dismiss the petition, arguing that Barr's sentence was proper even without the two robbery convictions because even excluding those convictions Barr had three other prior felony convictions when he was sentenced; the State attached to its motion a copy of the presentence investigation report showing that Barr had five felony convictions at the time he was sentenced. The circuit court summarily denied the petition on February 2, 2007, noting on the case-action summary that the petition was without merit as follows:

"The court finds that the defendant is correct in his assertion that the 2 robbery convictions in B[irming]ham Division of Jefferson Court CC-91-3880 and CC-91-3881 are no longer proper for consideration in sentencing under the Alabama Habitual Offender Act; however, as the State contends in its response, the defendant had 3 or more felonies excluding the 2 robbery charges. He had felony convictions in CC-93-801 (Etowah Co.), CC-91-3878 and CC-91-3879 (B[irming]ham Division — Jeff[erson] Co[unty])."

(C. 2.) Barr then filed a motion to reconsider in which he argued that the district attorney had presented only four prior felony convictions at his sentencing hearing and that the conviction in CC-93-801 was not presented by the State or relied on by the trial court for enhancement purposes at his sentencing hearing. The circuit court denied Barr's motion to reconsider on March 6, 2007, noting on the case-action summary that it found that Barr had been convicted of unlawful possession of a controlled substance in Etowah County and that "[o]n 8/25/93, therefore, [Barr] had 3 prior felony convictions at the time of sentencing on CC-01-0297." (C. 3.)

The record from Barr's direct appeal reflects that the State indicated before trial that Barr had five prior felony convictions and that the presentence investigation revealed five felony convictions. Barr testified at trial and admitted on direct examination and cross-examination that he had prior felony convictions for manslaughter, first-degree assault, and two counts of second-degree robbery; however, he was not asked about nor did he testify about any conviction for possession of a controlled substance in Etowah County. At sentencing, the State presented certified copies of only four felony convictions — a conviction for first-degree assault, a conviction for manslaughter, and the two robbery convictions that have since been set aside. Thus, it is apparent that Barr's sentence was enhanced based only on four prior felony convictions.

Section 13A-5-9, Ala. Code 1975, provides, in pertinent part:

"(b) In all cases when it is shown that a criminal defendant has been previously convicted of any two felonies and after such convictions has committed another felony, he or she must be punished as follows:

". . . .

"(3) On conviction of a class A felony, he or she must be punished by imprisonment for life or for any term of not less than 99 years.

"(c) In all cases when it is shown that a criminal defendant has been previously convicted of any three felonies and after such convictions has committed another felony, he or she must be punished as follows:

". . . .

"(3) On conviction of a class A felony, where the defendant has no prior convictions for any Class A felony, he or she must be punished by imprisonment for life or life without the possibility of parole, in the discretion of the trial court."

In McClintock v. State, 773 So.2d 1057 (Ala.Crim.App. 2000), we addressed a similar situation as follows:

"In his Rule 32 petition, which was filed on June 24, 1999, McClintock claimed that his life sentence for first-degree escape was illegal because, he said, one of the convictions that was used to enhance his sentence, specifically, his 1986 conviction in Jefferson County for the sale of a controlled substance, case no. CC-85-2744, had been set aside in January 1989. On October 12, 1999, the circuit court entered an order summarily dismissing McClintock's petition, stating as grounds that McClintock had raised this same claim in a prior postconviction petition, filed in February 1989, and that, therefore, his present petition was successive under Rule 32.2(b), Ala.R.Crim.P.

"The record reflects the[at] McClintock's first postconviction petition was summarily dismissed by an order of the circuit court entered in April 1989. In that order, the circuit [court] found that although McClintock's conviction in case no. CC-85-2744 had been, as McClintock alleged, set aside in January 1989, it was unnecessary to resentence McClintock because, the circuit court reasoned, McClintock's sentence of life imprisonment was within the range authorized under the Habitual Felony Offender Act for a defendant upon conviction of a Class B felony where the defendant has been previously convicted of any two felonies. See § 13A-5-9(b), Ala. Code 1975 ('In all cases when it is shown that a criminal defendant has been previously convicted of any two felonies and after such convictions has committed another felony, he must be punished as follows: . . . (2) On conviction of a Class B felony, he must be punished by imprisonment for life or for any term of not more than 99 years but not less than 15 years.')

"'"'[A] conviction that has been set aside or reversed may not be used to enhance [a] penalty.'" Prock v. State, 471 So.2d 519, 521 (Ala.Cr.App. 1985) (quoting 24B C.J.S. Criminal Law § 1960(6) (1962)).' Crenshaw v. State, 740 So.2d 478, 479 (Ala.Cr.App. 1998). Because McClintock's conviction in case no. CC-85-2744 was set aside in January 1989, McClintock was entitled to be resentenced for his first-degree escape conviction, with the circuit court considering only two prior felony convictions (i.e., the 1976 conviction in Shelby County for second-degree burglary and the 1980 conviction in Washington for first-degree robbery) for enhancement purposes under the Habitual Felony Offender Act. However, the circuit court's April 1989 order, which indicated merely that McClintock's life sentence was within the authorized statutory range, fails to establish that McClintock was properly resentenced using two prior felony convictions, rather than three, for enhancement. Because McClintock has not received a sentencing hearing at which only two prior felony convictions were considered for enhancement purposes, his sentence is illegal. Therefore, the claim in his present Rule 32 petition is not (as the circuit court found in its October 12, 1999, order of dismissal) subject to the procedural bar of Rule 32.2(b), Ala.R.Crim.P. See Jones v. State, 724 So.2d 75, 76 (Ala.Cr.App. 1998).

"Under § 13A-5-9(c)(2), Ala. Code 1975, a sentence of life imprisonment is mandatory upon conviction of a Class B felony where three prior felony convictions have been proven. However, under § 13A-5-9(b)(2), Ala. Code 1975, a broad range of possible sentences may be imposed upon conviction of a Class B felony where only two prior felony convictions have been proven. Notwithstanding the fact that, as the circuit court indicated in its April 1989 order, McClintock's sentence of life imprisonment was within the range authorized under the Habitual Felony Offender Act for a defendant upon conviction of a Class B felony where the defendant has been previously convicted of any two felonies, fundamental fairness requires that this cause be remanded for a new sentencing hearing, so that it may be established with certainty that the circuit court has exercised the discretion allowed it under § 13A-5-9(b)(2) in imposing McClintock's sentence. See Pickens v. State, 475 So.2d 637, 640 (Ala.Cr.App. 1985). Accordingly, this cause is remanded with directions for the circuit court to conduct a new sentencing hearing in accordance with this opinion. The circuit court may impose a sentence within the statutory range set forth in § 13A-5-9(b)(2), Ala. Code 1975. The circuit court should specifically state that it is resentencing McClintock without considering his conviction in case no. CC-85-2744."

773 So.2d at 1058-59 (emphasis omitted). See also Cole v. State, 951 So.2d 774 (Ala.Crim.App. 2006); Russaw v. State, 947 So.2d 429, 430-432 (Ala.Crim.App. 2006); McMillian v. State, 934 So.2d 434 (Ala.Crim.App. 2005); Capps v. State, 747 So.2d 358 (Ala.Crim.App. 1999); and Crenshaw v. State, 740 So.2d 478 (Ala.Crim.App. 1998).

Here, although there is some evidence in the trial record indicating that Barr had a fifth felony conviction at the time of sentencing, Barr did not admit to that conviction, the State did not prove the existence of that conviction at the sentencing hearing, and the trial court did not rely on that conviction in imposing the sentence. We cannot speculate whether the State could have proved the conviction had it attempted to. Further, the setting aside of two of the four convictions relied upon by the trial court in sentencing Barr impacted the sentencing range applicable to Barr. With three or more prior felony convictions, Barr was subject to either life imprisonment or life imprisonment without the possibility of parole under § 13A-5-9(c)(3), Ala. Code 1975, but with only two prior convictions, the range of punishment is life imprisonment or not less than 99 years' imprisonment under § 13A-5-9(b)(3), Ala. Code 1975; Barr could not receive the sentence he received — life imprisonment without the possibility of parole — with only two prior convictions. Under these circumstances, we cannot say that the error in Barr's sentence is harmless. Cf. Edwards v. State, 612 So.2d 1282 (Ala.Crim.App. 1992) (error in proving excess prior convictions above the number required to invoke the HFOA is harmless); Brown v. State, 784 So.2d 371, 372 (Ala.Crim.App. 2000) (holding that when a defendant admits he has prior felony convictions, those convictions are deemed proven for purposes of the HFOA); and Wright v. State, 709 So.2d 1318 (Ala.Crim.App. 1997) (holding that although the trial court improperly considered a fourth prior conviction, the error was harmless because the range of punishment prescribed for a defendant with three prior convictions was the same under the HFOA as the range prescribed for a defendant with four prior convictions). Thus, we conclude that Barr's sentence of life imprisonment without the possibility of parole, as currently imposed pursuant to § 13A-5-9(c)(3), is illegal, because two of the four convictions on which the trial court relied in imposing the sentence have been set aside since Barr's sentencing, and that, as in McClintock, fundamental fairness requires a new sentencing hearing.

We note that Barr may again be sentenced under the HFOA at the second sentencing hearing if the State gives proper notice to Barr of its intent to invoke the HFOA and of the prior convictions on which it intends to rely. We note further that the State is not limited at a second sentencing hearing to only the two surviving convictions on which it originally relied, but it may also attempt to prove any additional prior felony convictions of which it is aware.

"As this Court noted in Clements v. State, 709 So.2d 1321 (Ala.Crim.App. 1997):

"'In Nichols v. State, 629 So.2d 51 (Ala.Cr.App. 1993), this court stated that if resentencing was required, the defendant was entitled to be renotified of the State's intent to proceed under the HFOA and renotified of the convictions it intends to prove.

"""To enhance a defendant's sentence under the HFOA, the State must give proper notice of its intent to do so. The State must also give the defendant proper notice of the alleged previous felony convictions that it will attempt to prove at that sentencing hearing. If for whatever reason, another sentencing hearing is required and the State had notified the defendant of its intent to proceed under the HFOA at the previous sentencing hearing, then the State can re-notify the defendant of its intent to proceed under the HFOA and can notify the defendant that it will attempt to prove all previous felony convictions that the State is aware of, regardless of whether the State had attempted to prove those particular convictions at the previous sentencing hearing."'

"' Nichols v. State, 629 So.2d 51, 57 (Ala.Cr.App. 1993) (quoting Connolly v. State, 602 So.2d 452, 455 (Ala. 1992) (some emphasis [in Connolly]; some emphasis [in Clements])).

""'The rule is that the state may use, at a second sentencing hearing, convictions other than those used at the first hearing, provided that proper notice has been given prior to both hearings. Connolly v. State, 602 So.2d 452 (Ala. 1992); Jackson v. State, 566 So.2d 758 (Ala. 1990). See also A.R.O.P. 26.6(b)(3)(ii). 'This requires only that the defendant be notified before each sentencing hearing that the HFOA [Habitual Felony Offender Act] will be applied and what convictions the State will attempt to prove.' Connolly v. State, 602 So.2d at 454 (emphasis added [in Cooper])."

"' Cooper v. State, 632 So.2d 1342, 1343-44 (Ala.Cr.App. 1993), aff'd, 632 So.2d 1344 (Ala. 1994) ("The record in this case shows that the appellant was not given notice, prior to the third sentencing hearing, of the convictions the state intended to prove. At the hearing, the appellant made numerous and timely objections to the failure to give notice.").'

"709 So.2d at 1323."

Perry v. State, 861 So.2d 1, 3-4 (Ala.Crim.App. 2002) (some emphasis added). Thus, at Barr's second sentencing hearing, provided the State satisfies the notice requirement in Rule 26.6(b)(3)(ii), Ala.R.Crim.P. and its burden of proof in Rule 26.6(b)(3)(iii), Ala.R.Crim.P., the State may seek to enhance Barr's sentence under the HFOA with not only the assault and manslaughter convictions which were relied upon at Barr's first sentencing hearing, but also the unlawful-possession-of-a-controlled-substance conviction, which was not relied on at the first sentencing hearing, and with any other prior felony convictions of which it is aware.

Based on the foregoing, the judgment of the circuit court summarily denying Barr's petition is reversed and this cause remanded for the circuit court to grant Barr's petition and to conduct a new sentencing hearing in accordance with this opinion.

REVERSED AND REMANDED.

BASCHAB, P.J., and McMILLAN and WELCH, JJ., concur.

WISE, J., dissents.