Appellant challenges the trial court’s order summarily denying his postconviction motion filed pursuant to Florida Rule of Criminal Procedure 3.800(a). Because the trial court failed to attach portions of the record conclusively refuting appellant’s claim, we reverse.
Pursuant to a negotiated plea agreement, appellant pled guilty to two felonies and was sentenced to consecutive 10-year terms of imprisonment as an habitual violent felony offender (HVFO) on February 15, 1991. On December 21, 2000, the underlying predicate offense, a 1984 robbery conviction, was vacated by a Maryland court. Relying on the Maryland court’s opinion and order, appellant filed a rule 3.800(a) motion alleging that his sentence is illegal because the underlying predicate offense had been vacated.
If a defendant’s prior offenses do not qualify him as an habitual offender, an habitual offender sentence is illegal. Lee v. State, 731 So.2d 71, 73 (Fla. 2d DCA 1999). The fact that appellant entered into a negotiated plea agreement does not bar him from challenging the legality of his HVFO sentence. Lee, 731 So.2d at 73; Brown v. State, 609 So.2d 730, 732 (Fla. 1st DCA 1992).
A rule 3.800(a) motion may be an appropriate vehicle by which to challenge an HVFO sentence. Bover v. State, 797 So.2d 1246, 1251 (Fla.2001). However, appellant relies on extra-record facts. Therefore, the trial court should have treated his motion as a rule 3.850 motion. See, e.g., State v. Finelli, 780 So.2d 31 (Fla.2001) (indicating that a defendant may challenge an habitual offender sentence by a rule 3.850 motion if the predicate conviction is later reversed on appeal); Bozarth v. State, 789 So.2d 419, 420 (Fla. 2d DCA 2001) (holding that a rule 3.850 motion is the proper means by which to challenge an illegal sentence when the appellant relies on extra-record facts); Hall v. State, 643 So.2d 635, 636 (Fla. 1st DCA 1994) (holding that the courts have authority to treat a rule 3.800(a) motion as a rule 3.850 motion if it would be in the interest of justice to do so).
Although appellant’s motion was filed after the two-year period for filing a rule 3.850 motion had run, it raises a claim based on newly discovered facts, which is excepted from the two-year rule. See Fla. R.Crim. P. 3.850(b). To raise such a claim, the facts must have been (1) unknown by the defendant or his counsel at the time of sentencing, and (2) not discoverable by the defendant or his counsel by the use of due diligence. Rivera v. State, 717 So.2d 477, 483 (Fla.1998). Here, appellant was sentenced as an HVFO on February 15, 1991. The qualifying predicate conviction was not vacated by a Maryland court until December 21, 2000. Therefore, the Maryland court opinion and order are clearly newly discovered facts.
The trial court denied appellant’s claim as successive. However, the record establishes that this claim has never been decided on its merits. Thus, the claim is neither successive nor barred by the law of the case doctrine. See State v. McBride, *966848 So.2d 287 (Fla.2003); Zeigler v. State, 632 So.2d 48, 51 (Fla.1993); Fla. R.Crim. P. 3.850(b); see also Nicewonder v. State, 698 So.2d 376 (Fla. 1st DCA 1997).
Appellant has raised a facially sufficient claim that appears to have merit. Unless another qualifying predicate offense exists, appellant’s sentence must be vacated. Accordingly, on remand, the trial court shall either attach portions of the record conclusively refuting appellant’s claim or hold an evidentiary hearing.
We note that appellant’s sentence appears to have been the result of a negotiated plea. Should appellant prevail on remand, the state will be entitled to withdraw from the plea agreement if the agreement was negotiated, and one of its terms was that appellant would be sentenced as an HVFO. See Wade v. State, 822 So.2d 550, 551 (Fla. 1st DCA 2002).
REVERSED and REMANDED, with directions.
KAHN, WEBSTER and VAN NORTWICK, JJ„ CONCUR.