Defendant-Appellant Arturo Rojas-Luna (“Rojas-Luna”) appeals the sentence he received for violating 8 U.S.C. § 1326(a) by illegally entering the United States after previously being removed. Because we conclude that the district court’s use of Rojas-Luna’s 2006 removal for purposes enhancing his sentence pursuant to 8 U.S.C. § 1326(b)(2) was plainly erroneous, we VACATE Rojas-Luna’s sentence and REMAND for resentencing in conformance with this opinion.
I. FACTUAL AND PROCEDURAL BACKGROUND
Rojas-Luna, a citizen of Mexico who had previously been deported, was apprehended by United States Border Patrol agents on May 30, 2006, near Laredo, Texas. Because he lacked permission to be in the United States, Rojas-Luna was indicted for illegal reentry in violation of 8 U.S.C. § 1326(a). The indictment did not specifically describe any of Rojas-Luna’s prior removals or deportations, but generally alleged that Rojas-Luna had been previously removed or deported and had not received permission to reenter the country.
At his rearraignment on August 9, 2006, Rojas-Luna pleaded guilty to illegally reentering the United States. The factual basis for the charge, as described by the Government during the rearraignment, was that Rojas-Luna had been deported in 1988 and had reentered the United States on or about May 30, 2006, by wading the Rio Grande River. The district court accepted Rojas-Luna’s plea and set a date for sentencing.
The United States Probation Office then prepared Rojas-Luna’s Presentence Investigation Report (“PSR”), which assigned an initial offense level of eight to Rojas-Luna’s illegal reentry. See U.S.S.G. § 2L1.2(a). The PSR next recommended that Rojas-Luna’s offense level be increased by sixteen levels pursuant to United States Sentencing Guideline § 2L1.2(b)(l)(A), which authorizes a sixteen-level increase for aliens who reenter the country after being deported following a conviction for a crime of violence felony. The PSR noted that Rojas-Luna was convicted in 2003 of aggravated assault and removed in 2006 following his prison term. Factoring in a three-level reduction for acceptance of responsibility, Rojas-Luna’s total offense level was twenty-one. Combined with his criminal history score, the recommended sentencing range was seventy to eighty-seven months. Although the statutory maximum for illegal reentry is typically two years in prison, see 8 U.S.C. § 1326(a), Rojas-Luna’s 2003 conviction and subsequent removal raised the cap to twenty years pursuant to 8 U.S.C. § 1326(b)(2).
At his sentencing on December 16, 2006, Rojas-Luna objected on Apprendi1 grounds to the constitutionality of using his 2003 conviction to increase the statutory maximum sentence he could receive; however, he made no objection to the PSR’s use of his 2006 removal to increase the statutory maximum. The district court overruled the Apprendi objection and sentenced Rojas-Luna to seventy-three months in prison.
Rojas-Luna now appeals, arguing that his 2006 removal must have been proven to a jury beyond a reasonable doubt in order to increase the statutory maximum sentence he could receive under 8 U.S.C. *504§ 1326(b)(2). Rojas-Luna also renews his Apprendi objection for purposes of preserving his claim on that ground. We have jurisdiction pursuant to 28 U.S.C. § 1291 and now turn to the merits of our decision.
II. STANDARD OF REVIEW
Because Rojas-Luna did not object to the use of his 2006 removal before the district court, we review his claim on that ground for plain error. See United States v. Grant, 493 F.3d 464, 468 (5th Cir.2007). To prevail under the plain error standard, Rojas-Luna must demonstrate (1) an error, (2) that is clear or obvious, and (3) that affects his substantial rights. See United States v. McCrimmon, 443 F.3d 454, 458 (5th Cir.), cert. denied, 547 U.S. 1120, 126 S.Ct. 1931, 164 L.Ed.2d 679 (2006). If these three conditions are met, we may exercise our discretion to correct the error, but only if (4) the error “seriously affects the fairness, integrity, or public reputation of judicial proceedings.” Id. (internal quotation marks omitted).
III. DISCUSSION
On appeal, Rojas-Luna argues that the district court should not have been allowed to find the fact of his 2006 removal in order to increase the statutory maximum sentence he could receive; instead, Rojas-Luna asserts that such a finding must be made by a jury following proof beyond a reasonable doubt. The Government counters that Rojas-Luna’s 2006 removal is simply a sentencing factor that does not have to be proven to a jury. Before addressing the arguments of the parties, we first make clear why the 2006 removal is essential to the sentencing enhancement in the first place.
As noted above, the statute under which Rojas-Luna was convicted, 8 U.S.C. § 1326(a), provides for a maximum penalty of two years’ imprisonment for illegal reentry. However, pursuant to § 1326(b)(2), the maximum penalty is increased to twenty years in prison for an alien whose prior removal “was subsequent to a conviction for commission of an aggravated felony .... ” Id. (emphasis added). At his rearraignment, Rojas-Luna pleaded guilty to reentering the country after having been removed in 1988. Because he was not convicted of aggravated assault until 2003, his 1988 removal, although sufficient to convict him of violating § 1326(a), could not form the basis of the enhancement in § 1326(b)(2), because it was not “subsequent to” his conviction. See United States v. Sanchez-Mota, 319 F.3d 1, 3-4 (1st Cir.2002) (per curiam) (holding that § 1326(b)(2) did not apply to an alien who was not removed subsequent to his conviction). Consequently, under the plain terms of the statute, the Government must rely on Rojas-Luna’s 2006 removal in order to increase the maximum penalty range to twenty years. The question remains, then, whether the 2006 removal is a fact that must be proven beyond a reasonable doubt to a jury or if it may be found by the district judge at sentencing.
In Almendarez-Torres v. United States, 523 U.S. 224, 118 S.Ct. 1219, 140 L.Ed.2d 350 (1998), the Supreme Court held that a defendant’s prior conviction under § 1326(b)(2) was only a sentencing factor that did not need to be described in an indictment. Id. at 226-27, 118 S.Ct. 1219. The Government urges us to adopt the reasoning of Almendarez-Torres here and hold that a prior removal under § 1326(b)(2) is likewise only a sentencing factor and thus does not need to be proven to a jury. Rojas-Luna contends that this court must limit the holding of Almenda-rez-Torres to prior convictions alone.
Our review of Supreme Court precedent following Almendarez-Torres demon-*505states that, although Almendarez-Torres remains good law, the Supreme Court has shown a reluctance to expand Almenda-rez-Torres’s holding to any fact other than a prior conviction. For example, in Jones v. United States, the Court held that provisions in a carjacking statute that provided for higher penalties in cases involving serious bodily injury or death were elements of the offense itself, not sentencing factors. 526 U.S. 227, 229, 119 S.Ct. 1215, 143 L.Ed.2d 311 (1999). Similarly, in Appren-di, the Court determined that a law providing for higher penalties if a crime was racially motivated required a jury to find racial motivation beyond a reasonable doubt. 530 U.S. at 468-69, 497, 120 S.Ct. 2348.
In both Jones and Apprendi the Court noted the unique nature of its holding in Almendarez-Torres. The Jones Court discussed Almendarez-Torres’& focus on recidivism and reasoned that reliance upon prior convictions (recidivism) was appropriate because a prior conviction must be obtained through procedures that satisfy the constitutional guarantees of fair notice, reasonable doubt, and a jury trial. 526 U.S. at 248-49, 119 S.Ct. 1215. In Ap-prendi the Court distinguished Almenda-rez-Torres as “at best an exceptional departure” from prior law concerning what must be proven to a jury. Apprendi, 530 U.S. at 487, 120 S.Ct. 2348. Thus, neither Jones nor Apprendi counsels us to expand Almendarez-Torres beyond its current holding.
Perhaps the most significant statement by the Supreme Court on this issue comes from Apprendi where the Court stated that “[ojther than the fact of a prior conviction, any fact that increases the penalty for a crime beyond the prescribed statutory maximum must be submitted to a jury, and proved beyond a reasonable doubt.” 530 U.S. at 490, 120 S.Ct. 2348. It is thus clear that the Supreme Court will not countenance any expansion of Almenda-rez-Torres. This language also puts to rest the Government’s argument that the reasoning of Jones and Apprendi applies only to facts that are part of the commission of the crime itself, such as injury to the victim or the defendant’s racial motivation for the crime. While a prior conviction does not typically relate to the commission of a crime, it does not follow that any fact unrelated to the crime itself is exempt from the constitutional protection of a jury trial. The Supreme Court’s use of the phrase “any fact that increases a penalty” admits for no distinction between those facts that are related to the crime and those that are not.
The Government’s argument that we treat a prior removal as addressing the same recidivism concerns as a prior conviction is also unavailing. As noted above, one of the reasons the Supreme Court has countenanced the use of a prior conviction to enhance a sentence is that a prior conviction is the product of procedures that encompass the constitutional guarantees of fair notice, reasonable doubt, and a jury. Jones, 526 U.S. at 249, 119 S.Ct. 1215. Removals, on the other hand, are not subject to the same constitutional requirements. See Carlson v. Landon, 342 U.S. 524, 537, 72 S.Ct. 525, 96 L.Ed. 547 (1952) (“Deportation is not a criminal proceeding ... No jury sits. No judicial review is guaranteed by the Constitution.”); United States v. Benitez-Villafuerte, 186 F.3d 651, 657 (5th Cir.1999) (“A deportation hearing is a civil, not a criminal, action ... As such, the full range of constitutional protections available to a defendant in a criminal case are not afforded an alien in a deportation proceeding.”). Consequently, while a court may use a prior conviction with the knowledge that the defendant was given multiple constitutional protections, *506the same cannot be said for prior removals.
In sum, the Supreme Court has clearly indicated that Almendarez-Torres is limited to prior convictions and that any other fact used to increase a sentence beyond a statutory maximum must be proven to a jury. Therefore, the district court in this case erred in finding the fact of Rojas-Luna’s 2006 removal for purposes of increasing his sentence under § 1326(b)(2) beyond the statutory maximum.2 Further, in light of the above precedent, this error was clear and obvious, satisfying the first two elements of the plain error standard. We are not alone in this holding, as the Ninth Circuit has recently considered this issue and reached the same conclusion on materially indistinguishable facts. United States v. Covian-Sandoval, 462 F.3d 1090, 1096-99 (9th Cir.2006), cert. denied, — U.S. -, 127 S.Ct. 1866, 167 L.Ed.2d 355 (2007) (holding that it was plainly erroneous for the district court to find the fact of a subsequent removal for purposes of the § 1326(b)(2) enhancement when the defendant did not admit to the subsequent removal at the plea colloquy).
Our inquiry does not end there, however. Having determined that the district court plainly erred in using Rojas-Luna’s 2006 removal to enhance his sentence under § 1326(b)(2), we must now decide whether Rojas-Luna has shown that the error affected his substantial rights. McCrimmon, 443 F.3d at 458. An error affects a defendant’s substantial rights when the error “affected the outcome of the district court proceedings.” United States v. Palmer, 456 F.3d 484, 491 (5th Cir.2006) (internal quotation marks omitted). It is clear here that the error affected the outcome of the proceedings, as use of Rojas-Luna’s 2006 removal permitted the district court to give him a sentence above the otherwise-applicable statutory maximum of two years. See id. (holding that error resulting in additional sixty months’ sentence affected defendant’s substantial rights).
The Government urges us to follow the reasoning used in Covian-Sandoval, in which the Ninth Circuit determined that the erroneous use of a prior removal to increase a sentence under § 1326(b)(2) did not affect the defendant’s substantial rights. 462 F.3d at 1098-99. The Ninth Circuit’s decision, however, was based on its precedent in United States v. Minore that adopted a “more stringent” approach to the substantial rights analysis. 292 F.3d 1109, 1122 (9th Cir.2002) (cited by Covian-Sandoval, 462 F.3d at 1098). Under the Ninth Circuit’s approach in Mi-nore, a defendant is required to raise reasonable doubt that a rational jury would have found him guilty of the sentencing element absent the constitutional error before a court may conclude that the defendant’s substantial rights were affected. Id. at 1121-23 (rejecting the “less stringent” approach that simply asks if the defendant received a greater sentence than would have been permissible in light of the jury’s findings). Thus, in Coviartr-Sandoval, because the defendant could not raise reasonable doubt as to his prior removal, the court found no violation of substantial rights. Covian-Sandoval, 462 F.3d at 1098-99.
Our circuit has never adopted the reasonable doubt test as articulated in Mi-*507note, but instead has consistently held that a defendant may show that his substantial rights were affected simply by demonstrating that the outcome of the proceedings would have been different absent the error. Palmer, 456 F.3d at 491; McCrim-mon, 443 F.3d at 463. Given that Rojas-Luna received a sentence of seventy-three months in prison when, absent constitutional error, his sentence would have been a maximum of two years, we have little difficulty in concluding that Rojas-Luna’s substantial rights were affect.
As Rojas-Luna has satisfied the first three prongs of the plain error analysis, it remains for us to determine whether the error seriously affected the fairness, integrity, or public reputation of the judicial proceedings and, thus, warrants remediation. United States v. Puckett, 505 F.3d 377, 384 (5th Cir.2007). In United States v. Cotton, 535 U.S. 625, 627-29, 122 S.Ct. 1781, 152 L.Ed.2d 860 (2002), the Supreme Court considered whether the plain error inquiry was satisfied when a district court increased a defendant’s sentence based on conduct involving a certain quantity of drugs when the amount of drugs was not included in the indictment or found by the jury. While holding that there was plain error, the Court determined that there was no basis for concluding that the error seriously affected the fairness, integrity, or public reputation of judicial proceedings because the evidence of the drug amount that was presented at trial was “overwhelming” and “essentially uncontrovert-ed.” Id. at 633, 122 S.Ct. 1781 (internal quotation marks omitted).
In the present case, there was no trial at which evidence of Rojas-Luna’s 2006 removal might have been presented; there was only a plea colloquy at which the Government failed to set forth any evidence of the 2006 removal. The unsupported statement in Rojas-Luna’s PSR that he was removed in 2006 is not “overwhelming” evidence of the fact of his removal, particularly in light of the fact that there is no evidence in the record that Rojas-Luna ever agreed to the accuracy of the PSR. As a result, the plain error of the district court seriously affected the fairness and integrity of the proceedings, and, in the exercise of our discretion, we believe relief is warranted. Therefore, we VACATE Rojas-Luna’s sentence and REMAND this case for re-sentencing in conformance with this opinion.3
IV. CONCLUSION
Because use of Rojas-Luna’s 2006 removal to increase his sentence beyond the statutory maximum was plainly erroneous, we VACATE his sentence and REMAND this case for re-sentencing consistent with this opinion.
VACATED and REMANDED.