The government appeals Antonio Pedra-za-Mendoza’s 24-month sentence, imposed after he pled guilty to one count of illegal re-entry to the United States after having been previously deported and removed, in violation of 8 U.S.C. § 1326(a), (b)(2). On appeal, the government argues that the district court erred by concluding that a prior conviction must be charged as an element of the offense, in direct contravention of the Supreme Court’s precedent in Almendarez-Torres v. United States, 523 U.S. 224, 118 S.Ct. 1219, 140 L.Ed.2d 350 (1998). In response, Pedraza-Mendoza argues that any error was harmless because the district court would have imposed the same sentence regardless and the sentence was substantively reasonable under the circumstances. After careful review, we vacate and remand for re-sentencing.
We review constitutional sentencing issues de novo. See, e.g., United States v. Steed, 548 F.3d 961, 978 (11th Cir.2008). We are bound by prior precedent unless and until it is overruled by our Court sitting en banc or by the Supreme Court. United States v. Vega-Castillo, 540 F.3d 1235, 1236 (11th Cir.2008). We review the sentence a district court imposes for “reasonableness,” which “merely asks whether the trial court abused its discretion.” United States v. Pugh, 515 F.3d 1179, 1189 (11th Cir.2008) (quotation omitted).
In Almendarez-Torres, the Supreme Court addressed the statute at issue here, which increases the penalty for aliens who return to the United States after deportation without special permission from 2 years to 20 years if their prior deportation had come following the commission of an aggravated felony. 523 U.S. at 226, 118 S.Ct. 1219. The issue there, as here, was whether prior convictions were an element of the offense, or merely a sentencing factor that need not be set forth in the indictment. Id. at 227-28, 118 S.Ct. 1219. After analyzing the language of the statute and noting that recidivism is one of the most traditional sentencing factors, the Supreme Court held that a defendant’s prior conviction did not need to be alleged in the indictment or proven beyond a reasonable doubt if used for sentence enhancement purposes. Id. at 230-35, 247, 118 S.Ct. 1219. We’ve said that we are “bound by Almendarez-Torres until it is explicitly overruled by the Supreme Court.” United States v. Dowd, 451 F.3d 1244, 1253 (11th Cir.2006).
In this case, the district coui't erred by determining that Pedraza-Mendoza’s prior conviction for an aggravated felony *853should have been charged as an “element” of his illegal re-entry offense. This conclusion was in direct contravention of the Supreme Court’s clear, binding precedent, established under very similar facts, in Almendarez-Torres, 528 U.S. at 235, 247, 118 S.Ct. 1219. As we’ve held, Almendarez-Torres remains good law, since it has not been explicitly overruled by the Supreme Court, and therefore it still applies here. See Dowd, 451 F.3d at 1253.
As for Pedraza-Mendoza’s claim that the district court’s erroneous application of Almendarez-Torres was harmless, we disagree. In this Circuit, district courts must first correctly calculate the advisory sentencing range under the Guidelines, and then must determine a reasonable sentence in light of the factors listed in 18 U.S.C. § 3553(a). Pugh, 515 F.3d at 1189-90. An error in the district court’s calculation of the applicable guideline range warrants reversal, unless the error was harmless. United States v. Barner, 572 F.3d 1239, 1247 (11th Cir.2009). When a district court judge clearly states that he would impose the same sentence regardless of any error, then any error is harmless. United States v. Keene, 470 F.3d 1347, 1349-50 (11th Cir.2006). When that happens, the relevant “question then is whether the [sentence imposed] is reasonable, assuming exactly the same conduct and other factors in the case,” using the guideline range applicable without the error. Id. at 1350. If we determine on review that the sentence imposed was reasonable, it will be affirmed. Id. If, on the other hand, a district court commits an error and it is not-clear from the record whether the error affected the sentence, the sentence should be vacated. See United States v. Hall, 704 F.3d 1317, 1323 (11th Cir.2013).
In reviewing sentences for reasonableness, we typically perform two steps. Pugh, 515 F.3d at 1190. First, we ‘“ensure that the district court committed no significant procedural error, such as failing to calculate (or improperly calculating) the Guidelines range, treating the Guidelines as mandatory, failing to consider the § 3553(a) factors, selecting a sentence based on clearly erroneous facts, or failing to adequately explain the chosen sentence — including an explanation for any deviation from the Guidelines range.’ ” Id. (quoting Gall v. United States, 552 U.S. 38, 51, 128 S.Ct. 586, 169 L.Ed.2d 445 (2007)).1 Once we determine that a sentence is procedurally sound, we examine whether the sentence was substantively reasonable in light of the totality of the circumstances. Id.
If the court decides after “serious consideration” that a sentence outside the applicable guideline range is warranted, it must explain why that variance is “appropriate in a particular case with sufficient justifications.” Gall, 552 U.S. at 46, 128 S.Ct. 586. The justifications should be “sufficiently compelling to support the degree of the variance” and complete enough to allow for meaningful appellate review. Id. at 50, 128 S.Ct. 586. In reviewing a sentence outside the applicable guideline *854range, we take the degree of variance into account and ensure that the district court’s justifications for the variance are “sufficiently compelling,” but we must also give “due deference” to the district court’s decision that the § 3553(a) factors, as a whole, support the variance. United States v. Irey, 612 F.3d 1160, 1186-87 (11th Cir.2010) (en banc) (quotation omitted). The fact that we “might reasonably have concluded that a different sentence was appropriate” is not sufficient to justify reversal. Id. at 1187 (quotation omitted). We will vacate a sentence only if we are left with “the definite and firm conviction that the district court committed a clear error of judgment in weighing the § 3553(a) factors by arriving at a sentence that lies outside the range of reasonable sentences dictated by the facts of the case.” Id. at 1190 (quotation omitted).
Federal law prescribes a 20-year maximum sentence for an alien who illegally reenters the United States and whose deportation was subsequent to a conviction for an aggravated felony. 8 U.S.C. § 1326(b)(2). The statutory maximum for an alien who illegally re-enters the United States without such a felony is two years. Id. § 1326(a). When the statutory maximum sentence is less than the bottom of the applicable guideline range, the statutory maximum becomes the guideline range. U.S.S.G. § 5Gl.l(a).
Here, we cannot say that the district court’s error was harmless because its sparse discussion at the sentencing hearing makes it unclear whether its error in not applying Almendarez-Torres affected the imposed sentence. See Hall, 704 F.3d at 1323. Moreover, even if the district court would have reached the same result absent the error, the sentence imposed here was procedurally unreasonable. See Keene, 470 F.3d at 1349-50. If the court considered the applicable guideline range to be 24 months pursuant to U.S.S.G. § 5Gl.l(a) and 8 U.S.C. § 1326(a), it committed procedural error by applying the incorrect statutory maximum based on its erroneous Almendarez-Torres holding. See Barner, 572 F.3d at 1247. If, however, the court retained the applicable guideline range set forth in the pre-sentence investigation report, the sentence was still procedurally unreasonable because the district court provided no explanation for the significant downward variance from the applicable guideline range of 46 to 57 months’ imprisonment. Gall, 552 U.S. at 46, 50, 128 S.Ct. 586; United States v. Livesay, 525 F.3d 1081, 1093-94 (11th Cir.2008). Accordingly, we vacate Pedraza-Mendoza’s sentence and remand for re-sentencing.
VACATED AND REMANDED.