Petitioner Okey Garry Okpala requests review of the decision of the Board of Immigration Appeals ("BIA") affirming the immigration judge's ("IJ") deportation order. Because the BIA erred in construing 8 U.S.C. § 1227(a)(2)(A)(iii) to apply to an individual who was a naturalized citizen at the time of conviction, we grant the petition for review and vacate the BIA's deportation order.
I.
Okpala is a native of Nigeria who was admitted into the United States as a student in 1982.1 On December 8, 1986, Okpala became a permanent resident alien based on his marriage to a United States citizen. He was naturalized as a citizen on March 6, 1992. On October 25, 1993, Okpala was convicted of heroin conspiracy, distribution of heroin, importation of heroin, procuring citizenship unlawfully, and making false statements. His convictions were affirmed on direct appeal and the Supreme Court denied certiorari. United States v. Okpala , No. 93-9349, 1997 WL 154636, at *1 (11th Cir. 1997) (unpublished), cert. denied , 522 U.S. 1097, 118 S.Ct. 895, 139 L.Ed.2d 881 (1998). On December 1, 1993, the district court revoked Okpala's certificate of naturalization because of his conviction for procuring naturalization unlawfully. Okpala swore in his naturalization application that he had not knowingly committed any crime for which he had not been arrested. In light of the October convictions, this was false.
The Department of Homeland Security ("DHS") issued an Order to Show Cause in January 1994 and began deportation proceedings. The Government charged Okpala as being removable as an alien with controlled substance and aggravated felony convictions. Because Okpala was in the custody of the United States Bureau of Prisons serving his criminal sentence, an IJ administratively closed the immigration proceedings in May 1995. Twenty years later, in anticipation of Okpala's release, the DHS moved to recalendar Okpala's immigration proceedings and transfer the proceedings to the Immigration Court in Oakdale, Louisiana, where Okpala was detained.
*968The motion was granted on January 21, 2016.
Okpala moved to terminate his deportation proceedings. He argued that the order revoking naturalization was invalid and that he was a United States citizen. He initially conceded both charges of deportability before later denying them. The DHS submitted an exhibit with records of his criminal convictions. Okpala objected, arguing that the Government did not timely file the exhibit and the documents were insufficient. Okpala also argued that his 1993 convictions did not qualify as criminal convictions for immigration purposes. On May 31, 2016, the IJ denied the motion to terminate proceedings, because the denaturalization order sufficiently established that Okpala was no longer a United States citizen and the record contained sufficient evidence to establish the criminal convictions. The IJ additionally concluded that the heroin-related convictions were aggravated felonies that constituted violations of a law relating to a controlled substance.
Okpala filed a motion to reconsider the May 31, 2016 order and a second motion to terminate proceedings. Okpala challenged the determination that he was not a United States citizen and the validity of his 1993 criminal convictions. The IJ denied the motion to reconsider and the second motion to terminate and ordered that Okpala be deported to Nigeria.
Okpala appealed the IJ's denial of his motions to reconsider and terminate. He argued that, under Costello v. INS , 376 U.S. 120, 84 S.Ct. 580, 11 L.Ed.2d 559 (1964), he was a United States citizen at the time of the 1993 convictions, so he was not an alien under the general deportation statutes. He also contended that the denaturalization order was void for failure to comply with procedural and substantive provisions; the record of the 1993 convictions was untimely and lacked foundation; the DHS did not submit a "nonpoisonous" jury verdict of the 1993 convictions; the 1993 convictions constituted in absentia convictions and did not attain a substantial degree of finality; the instant removal proceeding was barred by collateral estoppel and res judicata; and his due process rights were violated.
The BIA concluded that the IJ properly determined that Okpala was convicted of an aggravated felony. The BIA also concluded that, under the doctrine of collateral estoppel, a prior denaturalization judgment conclusively established the ultimate facts in a subsequent deportation hearing. The BIA did not have jurisdiction to look at these ultimate facts and was precluded from reconsideration of issues of law resolved by the prior court arising from identical facts. The BIA noted that Okpala's denaturalization order was affirmed on appeal.
The BIA also determined that Okpala, now an alien, was amenable to deportation proceedings. The BIA distinguished Costello from the instant case on grounds that a judicial recommendation against deportation was unavailable to Okpala but had been central to Costello 's holding. As to the Due Process claim, the BIA determined that Okpala was afforded ample opportunity to present evidence on his behalf, had submitted substantial written and oral contentions to the IJ, and the IJ had considered those contentions. As Okpala failed to identify any specific action by the IJ resulting in actual prejudice, the BIA concluded that Okpala failed to show that the proceedings below were fundamentally unfair and dismissed the appeal. Okpala timely filed his petition for review.
II.
We review the BIA's findings of fact for substantial evidence; that review includes the IJ's judgment to the extent it influenced the BIA's decision.
*969Sealed Petitioner v. Sealed Respondent , 829 F.3d 379, 383 (5th Cir. 2016). The BIA's conclusions of law are reviewed de novo. Hernandez-De La Cruz v. Lynch , 819 F.3d 784, 785-86 (5th Cir. 2016). If "a conclusion embodies [the BIA's] interpretation of an ambiguous provision of a statute that it administers," we accord due deference as required by Chevron, U.S.A., Inc. v. Nat. Res. Def. Council, Inc. , 467 U.S. 837, 842, 104 S.Ct. 2778, 81 L.Ed.2d 694 (1984). Orellana-Monson v. Holder , 685 F.3d 511, 517 (5th Cir. 2012) (quotation omitted). Nevertheless, we "may reverse a decision that was decided on the basis of an erroneous application of the law." Sealed Petitioner , 829 F.3d at 384 (quoting Mikhael v. INS , 115 F.3d 299, 305 (5th Cir. 1997) ).
III.
Okpala contends that the BIA erred in construing 8 U.S.C. § 1227(a)(2)(A)(iii) to apply to him because he was a naturalized citizen at the time of his convictions. We agree.
"Any alien who is convicted of an aggravated felony at any time after entry is deportable." 8 U.S.C. § 1227(a)(2)(A)(iii). Section 1101(a)(3) of Title 8 of the United States Code defines an "alien" as "any person not a citizen or national of the United States." The parties concede that Okpala was a naturalized citizen when convicted of his crimes, but they disagree on the statute's application in this case. Okpala argues that 8 U.S.C. § 1227(a)(2)(A)(iii) does not apply to him because he was a naturalized citizen when convicted. The Government argues that Okpala's ab initio denaturalization makes him amenable to deportation under the statute.
Although this is a matter of first impression in this court, the Supreme Court addressed this issue in Costello v. INS , 376 U.S. 120, 84 S.Ct. 580, 11 L.Ed.2d 559 (1964). The Court in Costello considered the proposed deportation of Frank Costello, who was naturalized in 1925 and later denaturalized pursuant to 8 U.S.C. § 1451(a) for willful misrepresentations in his naturalization application. Costello , 376 U.S. at 121, 84 S.Ct. 580 ; see also Costello v. United States , 365 U.S. 265, 266, 81 S.Ct. 534, 5 L.Ed.2d 551 (1961). Costello claimed on his naturalization application that his occupation was "real estate" when in fact he was a "bootlegger." Costello , 365 U.S. at 270, 81 S.Ct. 534. In 1961, "the Immigration and Naturalization Service [ ("INS") ] commenced proceedings to deport" Costello pursuant to 8 U.S.C. § 1251(a)(4).2 Costello, 376 U.S. at 121, 84 S.Ct. 580. This provision reads in relevant part: "Any alien in the United States ... shall, upon the order of the Attorney General, be deported who ... at any time after entry is convicted of two crimes involving moral turpitude." Id. (emphasis added).
The Court considered whether Costello was subject to deportation under this statute "even though the two convictions relied upon to support deportation both occurred at a time when he was a naturalized citizen." Id. at 122, 84 S.Ct. 580. It concluded that he was not for two reasons. Id. First, the deportation provision was not status-neutral; it could not be construed to encompass denaturalized aliens who had not been aliens at the time of conviction. Id. at 122-23, 84 S.Ct. 580 (holding that "a person now an alien who was convicted of the two crimes in question while he was a naturalized citizen" is not deportable under the provision). Second, ab initio denaturalization pursuant to 8 U.S.C. § 1451(a) did not retroactively make such a person *970"an alien as a matter of law" at the time of conviction. Id. at 129, 84 S.Ct. 580. It is this second holding that controls the question of whether Okpala is amenable to deportation proceedings as an alien because of his ab initio denaturalization.
Like Costello, Okpala was naturalized when convicted of deportable offenses and then denaturalized pursuant to 8 U.S.C. § 1451(a) for material falsehoods on his naturalization application. And as in Costello , the Government brought deportation proceedings against Okpala under a subsection of the general deportation statute, 8 U.S.C. § 1227, that subjects an "alien" who "is convicted" of certain offenses to deportation. Costello is not materially distinguishable from the facts at hand and thus controls here.3 Accordingly, we conclude that Okpala was not rendered an "alien" at the time of conviction by nature of his subsequent ab initio denaturalization.4 Consequently, Okpala is not subject to deportation under 8 U.S.C. § 1227(a)(2)(A)(iii) because he was a naturalized citizen at the time he was convicted.
IV.
Okpala argues that his denaturalization decree was void for failing to comply with various procedural and substantive requirements, and as a result he is still a United States citizen. Okpala was convicted of unlawful citizenship under 18 U.S.C. § 1425. As such, "the court in which such conviction is had shall thereupon revoke, set aside, and declare void the final order admitting such person to citizenship, and shall declare the certificate of naturalization of such person to be canceled." 8 U.S.C. § 1451(e). The language of this statute is mandatory; the trial court cannot exercise discretion on the cancellation process. See United States v. Moses , 94 F.3d 182, 188 (5th Cir. 1996). Okpala's argument that he is a United States citizen is unmeritorious.
Okpala additionally argues that the doctrines of collateral estoppel and res judicata foreclosed the DHS from initiating removal proceedings because the issues were previously investigated when his 1994 detainer was cancelled and when the 2001 Order to Show Cause declared the denaturalization decree void. The DHS commenced deportation proceedings in January 1994 with the issuance of an Order to Show Cause. Because Okpala was in the custody of the Bureau of Prisons serving his criminal sentence, the immigration proceedings were closed in May 1995 and were not recalendared until twenty years later. This argument is unavailing.
Okpala also asserts that his due process rights were violated when he was not provided the opportunity to rebut the BIA's reliance on the collateral estoppel doctrine.
*971He contends that the BIA sua sponte applied the doctrine and that it was never raised below or mentioned in the IJ's order.
The Fifth Amendment's Due Process Clause protects individuals in removal proceedings. Manzano-Garcia v. Gonzales , 413 F.3d 462, 470 (5th Cir. 2005). As a general rule, due process requires that an alien be provided notice of the charges against him, a hearing before an executive or administrative tribunal, and a fair opportunity to be heard. Id. To prevail on a claim regarding an alleged denial of due process rights, an alien must make an initial showing of substantial prejudice. Anwar v. INS , 116 F.3d 140, 144 (5th Cir. 1997). Proving substantial prejudice requires an alien to make a prima facie showing that the alleged violation affected the outcome of the proceedings. Ogunfuye v. Holder, 610 F.3d 303, 306-07 (5th Cir. 2010) ; Anwar , 116 F.3d at 144-45. Assuming without deciding a due process violation occurred, Okpala fails to show that the outcome of the proceedings would have been different if he had the opportunity to respond to the collateral estoppel defense. See Ogunfuye , 610 F.3d at 306-07 ; Anwar , 116 F.3d at 144-45. Thus, this argument also fails.
Finally, Okpala argues that the IJ and BIA erroneously determined that collateral estoppel applied to the instant case, so the IJ and BIA did not address his affirmative defenses regarding the denaturalization order and the 1993 convictions. Because the denaturalization was mandated by statute, Okpala's convictions were affirmed on direct appeal, and the Supreme Court denied certiorari, the BIA correctly rejected his arguments regarding the validity of the denaturalization order and the 1993 convictions. See § 1451(e) ; Okpala , 1997 WL 154636, at *1 ; Okpala , 522 U.S. at 1097, 118 S.Ct. 895.
V.
For the foregoing reasons, we grant petition for review and vacate the deportation order.5
My able colleague has written reasonably based on the Supreme Court's decision in Costello v. INS , 376 U.S. 120, 84 S.Ct. 580, 11 L.Ed.2d 559 (1964), and I am constrained to concur. But under the Costello decision, this is an absurd result. Okpala was convicted on the same day of serious heroin trafficking charges, in which he engaged throughout his naturalization proceedings, and also of violating 18 U.S.C. § 1425, which criminalizes fraudulent procurement of citizenship, because of exactly the same trafficking. As the government points out, Okpala's denaturalization was automatic following the § 1425 conviction, see 8 U.S.C. § 1451(e).1 The six-week *972delay in the court's entry of a denaturalization order was mere formality.
Costello should be distinguishable because of the conjunction of reasons that exists here between the fraudulent naturalization and the heroin convictions. In Costello , the man's naturalization fraud concerned his misstatement of his occupation in 1925, while the tax evasion crimes leading to his deportability occurred and were prosecuted over twenty years later. Thus, the Court addressed the single question "whether this provision applies to a person who was a naturalized citizen at the time he was convicted of the crimes, but was later denaturalized ." 376 U.S. at 121, 84 S.Ct. at 581 (emphasis added). Given such a disconnect between the fraudulent naturalization and the later crimes, Costello was arguably defensible.
Here, however, Okpala was not "later" denaturalized. The underlying crime and naturalization fraud arise from exactly the same facts. Okpala flouted immigration law by applying for naturalization in October 1991; the indictment alleges he was participating in drug trafficking crimes from mid-1990 through 1991. He was dealing heroin while lining up at the immigration office to amend his status from legal permanent resident to a citizen. The facts that he secured naturalization in March 1992 before he was convicted in August 1993 are simply happenstances of official and bureaucratic timing. And as noted, his denaturalization was concomitant with his conviction. On these facts, I find it hard to conclude that Okpala's case involves the "relation back" doctrine condemned in Costello. Realistically, this is not so much a "relation back" case as a "relation to" case, since the fraudulent procurement is based on the same illegality as the drug trafficking perpetrated by the alien. A person denaturalized on this basis should not be able to claim the protection of fraudulently obtained United States citizen status.
Reading Costello to overturn Okpala's recent deportation means that the immigration consequences of precisely the same conduct differ for "naturalized" citizens and non-naturalized aliens solely because of the relative scheduling of the prosecution and the naturalization proceedings. The "naturalized" aliens will require two steps before they may be processed out of this country-denaturalization followed by a separate deportation proceeding-whereas aliens face the single remedy of deportation proceedings. Thus, Okpala (who has been deported) may return to the United States as a "legal permanent resident," only to face further deportation or inadmissibility proceedings based on his heroin trafficking convictions.
Because the Supreme Court wrote broadly in Costello, it imposed this illogical result.