ORDER
On June 4, 2003, Warren Lindsey entered a plea of guilty to the charge of possession of a firearm by a felon in violation of 18 U.S.C. § 922(g). Based on Lindsey's “substantial assistance,” the government presented a U.S.S.G. § 5K1.1 motion for a ten-percent downward departure in Lindsey’s sentence. Without the reduction, Lindsey’s guideline range was 110-137 months based on his criminal history category of VI and his total offense level of 25. The district court granted the government’s downward departure motion and reduced Lindsey’s sentence to 96 months. However, just prior to imposing this sentence, the district court heard from Lindsey during allocution, and decided sua sponte to reduce Lindsey’s sentence to 60 months. The court reasoned that the second downward departure was merited because Lindsey’s criminal history category overrepresented his past conduct. Neither party sought a downward a departure based on overrepresentation of the defendant’s criminal history category and the presentence report (PSR) did not recommend such a departure. The government now appeals the court’s decision to disregard the 96-month sentence and impose the 60-month sentence. The government asserts that the district court failed to provide adequate notice as required by *512Rule 32(h) of the Federal Rules of Criminal Procedure. We agree, and consequently reverse and remand for re-sentencing.
I. BACKGROUND
In his plea agreement, Lindsey stipulated to the following facts:
On November 4, 2002, Bloomington, Illinois Police responded to a report of a robbery. The victim had been a passenger in a car driven by a female and in which the defendant was also riding. The victim stopped the car and pointed it out to the police. The police stopped the car and the female and the victim both identified the defendant, Warren E. Lindsey, as the person who had held a gun on the victim and robbed him of $130. The police seized a .25 caliber Ravens Arms handgun, Serial No. 1263948 from the defendant. After the defendant was Mirandized, he admitted the robbery.
Applying U.S.S.G. § 2K2.1(a)(2), for the unlawful possession of firearms, the court set the defendant’s base offense level at 24. It then enhanced his base offense level four points, pursuant to § 2K2.1(b)(5), because the firearm was used during an armed robbery. Finally, the court reduced Lindsey’s total offense level by three points based on his acceptance of responsibility pursuant to U.S.S.G. § 3El.l(a), resulting in a total offense level of 25.1 The PSR placed Lindsey in criminal history category VI based on his prior convictions for aggravated battery in 1995, domestic battery in 1998, domestic battery and aggravated battery in 1998, and obstruction of justice in 2001 and because he committed the underlying offense both while on parole and within two years of being released from prison.2 Neither the government nor the defendant lodged any objections to the district court’s acceptance of the PSR.
As agreed upon by the parties, the government moved for a downward departure based on Lindsey’s substantial assistance pursuant to U.S.S.G. § 5K1.1. Specifically, the government suggested a downward departure of ten percent, which would have resulted in a 99-month sentence. The defense, permitted to comment, suggested a further reduction to 96 months. The district court granted the government’s motion for downward departure *513but sentenced the defendant to 96 months in accordance with the defendant’s suggestion.
Prior to imposing the sentence, the district court heard from the defendant during allocution. Lindsey briefly described the circumstances of some of his prior convictions and arrests. After listening to the defendant, the district court indicated that it was going to further depart downward to 60 months. The government requested that the district court explain its reasoning, to which it responded that the defendant’s criminal history category of VI overrepresented the seriousness of his past crimes and likelihood of recidivism.
II. ANALYSIS
As the government did not formally object to the court’s decision to depart, we review a district court’s decision to downward depart de novo. United States v. Mallon, 345 F.3d 943, 945-47 (7th Cir.2003). However, we review the district court’s decision not to give notice of its decision to downward depart for plain error because the government did not object in the court below. United States v. Carroll, 346 F.3d 744, 747 (7th Cir.2003). “Plain error exists when there is an error which is clear or obvious and which affects substantial rights.” United States v. Otis, 107 F.3d 487, 489 (7th Cir.1997).
According to Rule 32(h) of the Federal Rules of Criminal Procedure “{bjefore the court may depart from the applicable sentencing range on a ground not identified for departure either in the presentence report or in a party’s prehearing submission, the court must give the parties reasonable notice that it is contemplating a departure.” See also Burns v. United States, 501 U.S. 129, 135, 111 S.Ct. 2182, 115 L.Ed.2d 123 (1991) (holding that the district court must give sufficient notice to defendants prior to departing to allow “full adversary testing of the issues”). Both parties agree that the district court was required to give the government and the defendant notice of its decision to downward depart. Therefore, the district court plainly erred by ruling on the issue sua sponte without affording the parties an opportunity to be heard and we must remand for resentencing.
The real dispute concerns the scope of the remand. See 28 U.S.C. § 2106; United States v. Young, 66 F.3d 830, 835 (7th Cir.1995) (finding that § 2106 permits this court to order the district court to either tailor the remand to specific issues or conduct a complete resentencing); United States v. Polland, 56 F.3d 776, 777 (7th Cir.1995). The government contends that Lindsey has waived any right to argue overrepresentation of his criminal history category. Ordinarily, a defendant’s acceptance of, or failure to challenge, the court’s calculation of his criminal history results in a waiver of that argument on appeal. United States v. Redding, 104 F.3d 96, 99 (7th Cir.1996). However, here the question is not the defendant’s waiver or forfeiture of an objection, but rather the district court’s determination that the PSR was somehow inaccurate. As Rule 32(h) recognizes, the district court may, in its discretion, order the parties to brief a legal issue concerning a defendant’s sentence.
Because neither party had the opportunity to present the district court with a developed legal argument, we remand for resentencing. Should the district court be inclined to revisit the question of Lindsey’s criminal history category, it has the discretion to do so if it first affords the parties a meaningful opportunity to be heard in accordance with Rule 32(h). While we do not reach the issue of the applicability of the downward departure based on over-representation, as the district court should be the first to assess that issue, we do note *514that § 4A1.3(b)(l) of the guidelines permits a downward departure by the district court only when “reliable information indicates that the defendant’s criminal history category substantially over-represents the seriousness of the defendant’s criminal history or the likelihood that the defendant will commit other crimes.... ” In United States v. Bradford, 78 F.3d 1216, 1223 (7th Cir.1996) (quoting United States v. Abbott, 30 F.3d 71, 73 (7th Cir.1994)), we reiterated our position that a departure under § 4A1.3 is “available only when ‘a defendant’s criminal history significantly over-represents the seriousness of his past conduct.” ’
III. CONCLUSION
The defendant’s sentence is VACATED and this case is REMANDED for resentencing. We also order that the PSR be sealed.
. We note that the departures in this case does not implicate our recent decision in United States v. Booker, 375 F.3d 508 (7th Cir.2004). In Booker, we reasoned that the Court's holding in Blakely v. Washington, - U.S. -, -, 124 S.Ct. 2531, 2536, 159 L.Ed.2d 403 (2004), that "the 'statutory maximum’ for Apprendi [v. New Jersey, 530 U.S. 466, 120 S.Ct. 2348, 147 L.Ed.2d 435 (2000)] purposes is the maximum sentence a judge may impose solely on the basis of the facts reflected in the jury verdict or admitted by the defendant” (emphasis in original), applied to the federal sentencing guidelines. Id. at 510, 120 S.Ct. 2348. Here, the four point enhancement under § 2K2.1(b)(5) was fully supported by the defendant’s stipulations in his plea agreement and did not require any judicial fact finding.
. Lindsey's criminal history computation also seems undisturbed by Booker. As only the Supreme Court can overturn its precedent, this calculation seems permissible in light of Almendarez-Torres v. United States, 523 U.S. 224, 244, 118 S.Ct. 1219, 140 L.Ed.2d 350 (1998), which held that prior felony convictions were sentencing factors which need not be charged in an indictment or proven beyond a reasonable doubt as they are not elements of the charged offense. See id. (stating that "to hold that the Constitution requires that recidivism be deemed an 'element' of petitioner’s offense would mark an abrupt departure from a longstanding tradition of treating recidivism as 'go[ing] to the punishment only.’ ”). It also seems supported by Apprendi’s, 530 U.S. at 490, 120 S.Ct. 2348, express exclusion of prior convictions from its heightened standard of proof requirement.