Javier Noriega-Lopez is a citizen and national of Mexico admitted to the United States as a lawful permanent resident alien about thirty-six years ago. In March 2000, Noriega-Lopez was convicted of felony possession of heroin for sale in violation of California Health and Safety Code § 11351, an offense classified as an aggravated felony and a controlled substance offense under the Immigration and Nationality Act (“INA”). See 8 U.S.C. §§ 1227(a)(2)(A)(iii); (B)(i). Shortly thereafter, the Immigration and Naturalization Service (“INS”) issued a Notice to Appear charging Noriega-Lopez with removability for his crime. Noriega-Lopez denied that he had been convicted as stated in the Notice to Appear. At a removal hearing on July 17, 2000, the Immigration Judge (“IJ”) reviewed the INS’s proffer of documentation and concluded that the agency’s showing was inadequate to prove by clear and convincing evidence that Noriega-Lopez had been so convicted. See 8 U.S.C. § 1229a(c)(3)(A) (“the Service has the burden of establishing by clear and convincing evidence that, in the case of an alien who has been admitted to the United States, the alien is deportable”). The IJ focused on the fact that the criminal complaint issued to Noriega-Lopez was captioned “Superior Court of California, County of San Joaquin,” while the conviction document, signed by Noriega-Lopez, was identified as emanating from the “Municipal Court of California, County of San Joaquin, Stockton Judicial District.” As a result of his determination that the INS did not meet its evidentiary burden, the IJ terminated removal proceedings.

The INS appealed this decision, requesting “that the Board [of Immigration Appeals] reverse the Immigration Judge’s ruling terminating these removal proceedings and that said proceeding be remanded to the Immigration Court for further proceedings.” On July 31, 2001, the Board of Immigration Appeals (“BIA”) sustained the INS’s appeal on the ground that the record clearly established Noriega-Lopez’s conviction. The BIA found the Municipal Court conviction document an adequate basis for the INS’s institution of removal proceedings, stating: “The bottom line is that the record clearly establishes that the respondent was convicted for the offense of possession of a designated controlled substance (heroin) for sale in violation of section 11351 of the California Health and Safety Code.” The BIA vacated the IJ’s order. Rather than remanding as requested by the INS, the BIA ordered Noriega-Lopez removed to Mexico.

Noriega-Lopez filed a petition for review with this Court. We directed him to show cause why the petition should not be dismissed for lack of jurisdiction, and stayed Noriega-Lopez’s removal. Instead of demonstrating why this Court had jurisdiction, Noriega-Lopez moved for voluntary dismissal. His motion was granted, as was his request that the temporary stay remain in effect.

On-November 8, 2001, Noriega-Lopez filed a habeas petition in the district court, alleging that the INS had failed to meet its burden of proving his conviction and that the BIA had usurped the authority of the IJ by entering its own order of removal without first allowing Noriega-Lopez an opportunity to apply for relief. The district court denied the petition, holding that it lacked jurisdiction to consider Noriega-Lopez’s challenge concerning his alleged conviction: “[T]he determination of whether petitioner was ‘convicted’ of an aggravated felony should have been made by the Ninth Circuit. Petitioner, having failed to raise this issue in response to the Ninth Circuit’s order to show cause, should not now be allowed to present that issue to this court on habeas.”

In the alternative, the district court found that even if it had jurisdiction over Noriega-Lopez’s failure of proof claim, “the record contains clear and convincing proof that petitioner was convicted by the California Superior Court,” attributing the discrepancy on Noriega-Lopez’s conviction form to a recent merger of the superior and municipal courts into a unified superi- or court. “During the transition period, the superior court issuing petitioner’s conviction continued to use municipal court forms while it waited for updated forms.... Under these circumstances, granting the petition indeed would elevate form over substance.”

Addressing Noriega-Lopez’s challenge to the BIA’s failure to remand his case to the IJ, the district court rejected the argument on the merits, because “petitioner has not provided any evidence to show that he is entitled to relief from removal, or even alleged that he is entitled to such relief. As such, remanding this case ... would be futile and an unnecessary waste of judicial resources.”

Subsequent to filing his appeal with this Court, Noriega-Lopez was removed from California to Mexico. We retain jurisdiction over a removed alien’s habeas petition when, as here, it was filed before removal took place and there are collateral consequences arising from the removal. See Zegarra-Gomez v. INS, 314 F.3d 1124, 1125 (9th Cir.2003).

DISCUSSION

We review the district court’s denial of Noriega-Lopez’s habeas petition de novo. See Singh v. Ilchert, 63 F.3d 1501, 1506 (9th Cir.1995).

Noriega-Lopez argues, first, that we have jurisdiction to review his insufficient documentation contention, now couched as a due process claim. The INS counters that Noriega-Lopez could have raised that claim on direct review. Because Noriega-Lopez voluntarily abandoned his petition for review, the INS posits, he failed to exhaust an available judicial remedy and relief should not be available. See Castro-Cortez v. INS, 239 F.3d 1037 , 1047 (9th Cir.2001) (“we require, as a prudential matter, that habeas petitioners exhaust available judicial and administrative remedies before seeking relief under [28 U.S.C.] § 2241”). We agree with the INS and therefore affirm this aspect of the district court’s decision.

Noriega-Lopez is correct that the jurisdiction-stripping provision of 8 U.S.C. § 1252 (a)(2)(C) deprives us of jurisdiction over constitutional as well as other questions presented in a petition for review filed by an individual removed because he or she committed a qualifying criminal offense. See Flores-Miramontes v. INS, 212 F.3d 1133, 1135-36 (9th Cir.2000); see also Cedano-Viera v. Ashcroft, 324 F.3d 1062, 1064, 1067 (9th Cir.2003) (reaffirming this principle after Calcano-Martinez v. INS, 533 U.S. 348 , 121 S.Ct. 2268 , 150 L.Ed.2d 392 (2001)); Randhawa v. Ashcroft, 298 F.3d 1148, 1154 (9th Cir.2002) (same). Because constitutional claims raised by criminal aliens can be raised in habeas corpus proceedings, we have de- dined to construe the statute so as to permit direct review by this Court. Flores-Miramontes, 212 F.3d at 1143 . Constitutional claims such as that of Flores-Miramontes, a controlled substance offender who raised a due process challenge to the BIA’s application of a filing deadline when the INS was alleged to have caused the relevant delay, see id. at 1135 , are therefore cognizable if at all on habeas, not direct review.

At the same time, we have recognized that in determining the effect of 8 U.S.C. § 1252 (a)(2)(C) on our jurisdiction directly to review a particular case, we must investigate the alleged underlying conviction as thoroughly as is necessary to ascertain whether the jurisdictional bar applies. As stated in Ye v. INS, 214 F.3d 1128, 1131 (9th Cir.2000):

It does not matter, contrary to Noriega-Lopez’s submission, that his contention concerns not whether the alleged conviction was for an aggravated felony but whether he was convicted at all. Noriega-Lopez’s due process claim regarding the sufficiency of the evidence used by the INS to establish his conviction falls squarely within the scope of the jurisdiction-determining analysis that this Court has conducted on direct review. See, e.g., Pazcoguin v. Radcliffe, 292 F.3d 1209, 1212 (9th Cir.2002) (“We have repeatedly held that we retain jurisdiction to determine whether an alien in fact committed acts that would trigger [the INA’s jurisdictional bar for controlled substance offenses.] Because the central issue here is whether Pazcoguin in fact admitted to committing the essential elements of a controlled substance violation, we have jurisdiction.” (citations omitted)); Dillingham v. INS, 267 F.3d 996, 1003 (9th Cir.2001) (holding, in a case where petitioner alleged that his conviction had been expunged, that “we have jurisdiction to determine whether the facts relevant to our jurisdiction exist”); Zavaleta-Gallegos v. INS, 261 F.3d 951, 955 (9th Cir.2001) (reviewing the BIA’s factual findings concerning whether petitioner’s conviction for a crime of moral turpitude was waived, as the question was determinative of the Court’s jurisdiction under 8 U.S.C. § 1252 (a)(2)(C)); Matsuk v. INS, 247 F.3d 999, 1001 (9th Cir.2001) (examining whether petitioner had committed an aggravated felony because “[p]art of having jurisdiction to determine our jurisdiction includes having jurisdiction to review threshold issues.” (internal quotation marks and citation omitted)). What unites these cases is their common inquiry into whether petitioners’ convictions were valid and, consequently, jurisdiction-stripping.

Thus, the sufficiency of the evidence mustered by the INS to demonstrate Noriega-Lopez’s conviction is precisely the type of “threshold issue” that we can review on direct appeal. This is true regardless of whether the issue is labeled as “sufficiency of the evidence” or “due process.” See Luu-Le v. INS, 224 F.3d 911 , 914 n. 1 (9th Cir.2000) (“Simply because Luu-Le has framed his argument in the constitutional terms of ‘due process’ and ‘fundamental fairness’ in this direct appeal does not mean that we have a basis for jurisdiction independent of [ 8 U.S.C. § 1252 (a)(2)(C)’s] removal of such jurisdiction.”). Without clear and convincing evidence of his conviction, Noriega-Lopez would not be removable, as only that con viction supported the INS’s allegation of removability. Answering the question whether a petitioner was indeed convicted of an aggravated felony and/or a controlled substance offense goes to the heart of our jurisdictional determination under 8 U.S.C. § 1252 (a)(2)(C). The present ease is indistinguishable from our precedents so holding, Noriega-Lopez’s arguments to the contrary notwithstanding.

Noriega-Lopez should therefore have raised his challenge to the INS’s evidence of his conviction on direct review. We will not consider it now. See Castro-Cortez, 239 F.3d at 1047. The district court’s denial of relief to Noriega-Lopez on this ground was correct.

Noriega-Lopez also argues that, after resolving the INS’s administrative appeal concerning the adequacy of the proof of conviction, the BIA did not have authority to enter its own removal order but was obliged to remand to the IJ for further proceedings.

As to this contention that the BIA’s purported order of removal was improper, no direct review was available. The claim only arises if the question concerning removability based on a covered criminal conviction is first finally resolved in the INS’s favor. Here, the failure to raise that question before this Court on direct review has resulted in such a final resolution of the conviction issue. And, under § 1252(a)(2)(C), we lack jurisdiction on direct review over challenges to an order of removal against an acknowledged aggravated felon and/or controlled substance offender. We thus had no jurisdiction on direct review to consider the ultra vires question Noriega-Lopez has raised in his habeas petition. The district court therefore properly exercised jurisdiction over the issue. See Flores-Miramontes, 212 F.3d at 1143 .

The INS argues that Noriega-Lopez failed to exhaust his administrative remedies, because he “could have moved the Board to reopen or reconsider its decision so that he could apply for relief from removal,” and that the district court should have declined to exercise its habeas jurisdiction for that reason. This argument implicitly draws on 8 U.S.C. § 1252 (d)(1), which directs that “[a] court may review a final order of removal only if ... the alien has exhausted all administrative remedies available to the alien as of right.” Assuming without deciding that this provision applies in the habeas context, we find that there was no failure to exhaust within the meaning of § 1252(d)(1).

In discussing exhaustion of remedies prior to direct review, Castro-Cortez explained that “because the BIA need not actually reopen its prior decision, a motion to reopen is considered a request for discretionary relief, and does not constitute a remedy that must be exhausted.” 239 F.3d at 1045. Here, a motion to reopen would not have been appropriate, as there were no new facts relevant to the propri ety of the BIA’s issuance of the order of removal. See 8 C.F.R. § 1003.2 (c)(1) (“A motion to reopen proceedings shall not be granted unless it appears to the Board that evidence sought to be offered is material and was not available and could not have been discovered or presented at the former hearing....”); Iturribarria v. INS, 821 F.3d 889, 895 (9th Cir.2003) (discussing the distinction between motions to reopen and motions to reconsider). The same regulation that renders a motion to reopen discretionary, however, also applies to motions to reconsider. See 8 C.F.R. § 1003.2 (a) (“The decision to grant or deny a motion to reopen or reconsider is within the discretion of the Board, subject to the restrictions of this section.” (emphasis added)). Indeed, we routinely assert jurisdiction over cases decided by the BIA in which no motion to reconsider was filed, even though all aliens filing petitions for review necessarily contend that there were “errors of fact or law in the prior Board decision.” Id. § 1003.2(b)(1) (specifying requirements for fifing motions to reconsider); see also Iturribarria, 321 F.3d at 895 (“The only supporting materials required for a motion to reconsider are a statement of the party’s arguments regarding the BIA’s alleged errors and ‘pertinent authority.’ It is implicit in subsection (b)(1) that the BIA will reconsider the party’s case using the same record evidence used in making its prior decision.”).

It follows that motions to reconsider, like motions to reopen, are not “remedies available ... as of right” within the meaning of 8 U.S.C. § 1252 (d)(1). The INS’s contention that Noriega-Lopez was obliged to file a motion to reopen or reconsider before seeking review of the BIA’s order of removal is erroneous. Aside from statutory exhaustion requirements, courts may prudentially require habeas petitioners to exhaust administrative remedies. See Castro-Cortez, 239 F.3d at 1047 (“we require, as a prudential matter, that habeas petitioners exhaust available judicial and administrative remedies before seeking relief under [28 U.S.C.] § 2241”). We have enunciated the prudential considerations weighing in favor of requiring agency exhaustion as whether “(1) agency expertise makes agency consideration necessary to generate a proper record and reach a proper decision; (2) relaxation of the requirement would encourage the deliberate bypass of the administrative scheme; and (3) administrative review is likely to allow the agency to correct its own mistakes and to preclude the need for judicial review.” Montes v. Thornburgh, 919 F.2d 531, 537 (9th Cir.1990).

These circumstances are not present here: We have a proper record available, the ultra vires contention is purely one of statutory construction, and the BIA necessarily decided the legal question of its authority to issue removal orders in the first instance by issuing an order of removal ab initio, rejecting the INS’s specific request for a remand. There was no deliberate bypass of the administrative scheme. Rather, the BIA decided a question not presented to it by the parties. Noriega-Lopez in no way encouraged that approach, so any bypass of the usual administrative exploration of issues was the fault of the BIA itself, not the petitioner. As explained above, moreover, the only avenue of relief available to Noriega-Lopez, a motion to reconsider, was not available as of right, so there is no basis for concluding that the fifing of such a motion would likely have precluded the need for judicial review.

We conclude that the district court properly exercised its habeas jurisdiction over Noriega-Lopez’s ultra vires contention. We do not, however, agree with the district court’s resolution of that issue.

In assessing Noriega-Lopez’s argument that the BIA acted ultra vires in issuing his removal order in the first instance, we interpret the INA in light of the amendments enacted by the Antiterrorism and Effective Death Penalty Act (“AED-PA”), Pub. L. No. 104-132, 110 Stat. 1214 (Apr. 24, 1996), and the Illegal Immigration Reform and Immigrant Responsibility Act of 1996 (“IIRIRA”), Pub. L. No. 104-208,110 Stat. 3009 (Sept. 30,1996).

Before the enactment of IIRIRA, the BIA “retained enormous discretionary power.” Ramirez-Alejandre v. Ashcroft, 320 F.3d 858, 864 (9th Cir.2003) (en banc). Its authority was not, however, unlimited. Rather, the BIA, then as now, was only “vested with the authority to exercise the discretion granted by the Attorney General consistent with the statutory requirements.” Id.

The INA as amended by AEDPA and IIRIRA spells out with fine cut precision the manner in which the Attorney General is to exercise his authority to order aliens removed administratively, namely, through proceedings instigated by the INS before IJs that result in orders issued in the first instance by those judges. See 8 U.S.C. § 1229a(a)(l)-(3) (“An immigration judge shall conduct proceedings for deciding the inadmissibility or deportability of an alien.... Unless otherwise specified in this chapter, a proceeding under this section shall be the sole and exclusive procedure for determining whether an alien may be ... removed from the United States.”). AEDPA added for the first time a definition of “order of deportation.” See 8 U.S.C. § 1101 (a)(47)(A); AEDPA § 440, 110 Stat. at 1277. That definition reads:

Section 1101(a)(47) goes on in subsection (B) to provide:

Under this statutory scheme, only an IJ (or another administrative officer designated by the Attorney General, a provision not applicable here), may issue orders of deportation. The BIA (in its sole appearance in the statute) is restricted to affirming such orders, not issuing them in the first instance.

The legislative history of the AEDPA amendments affecting criminal aliens such as Noriega-Lopez confirms that, in enacting the jurisdictional bar now contained in 8 U.S.C. § 1252 (a)(2)(C), Congress envisioned a sequential process involving (1) entry of a removal order by an IJ and (2) subsequent review of this order by the BIA. A principal architect of the reforms, then-Senator Abraham, stated that the provisions would:

141 Cong. Rec. S7823 (daily ed. June 7, 1995) (emphasis added).

Other newly added provisions of the current INA also indicate that Congress intended this division of authority. Under 8 U.S.C. § 1252 (b)(3)(A), petitions for judicial review of removal orders must “be served on the Attorney General and on the officer or employee of the Service in charge of the Service district in which the final order of removal under [8 U.S.C. § 1229a] was entered.” In Noriega-Lopez’s case, originating in Arizona, it would make no sense to have served Noriega-Lopez’s petition for judicial review on the person in charge of the Service district in which the BIA is located. That individual, who is in Norfolk, Virginia, has nothing to do with the instant proceedings. Today’s INA, therefore, does not contemplate that the BIA may issue a final order of removal in the absence of such an order by the IJ. See also 8 U.S.C. § 1256 (a) (“an order of removal issued by an immigration judge shall be sufficient to rescind the alien's status” (emphasis added)); see generally United States v. Robles-Rodriguez, 281 F.3d 900, 904 (9th Cir.2002) (we cannot interpret one provision of a statute “in a manner that renders other sections of the same statute inconsistent, meaningless or superfluous.” (internal quotation marks and citation omitted)).

In sum, the present statute specifies in no uncertain terms that it is IJs who are to issue administrative orders of removal in the first instance. There is no indication in the statute that the BIA may do so.

We consider it telling in this regard that the outcome sought by the INS on appeal to the BIA in this case was not the eventual result reached by the BIA, entry of an order of removal. Instead, the Service “respectfully requested] that the Board reverse the Immigration Judge’s ruling terminating these removal proceedings and that said proceeding be .remanded to the Immigration Court for further proceedings.” (Emphasis added.) At that juncture, if not now, the INS apparently recognized that current BIA authority does not include entry'of orders of removal for aliens against whom no such order was issued by the IJ. Rather, the BIA’s authority is limited to affirming orders of removal previously issued by the IJ or, where. the IJ refused to issue such an order on the INS’s application for one, reversing the IJ’s ruling terminating the proceedings and remanding.

The INS provides no convincing rationale for its contrary reading of the current statutory and regulatory regime. Instead, the INS refers to regulations that formerly gave the BIA broad powers to “exercise such discretion and authority conferred upon the Attorney General by law as is appropriate and necessary for the disposition of the case,” see 8 C.F.R. § 3.1 (d)(1) (2002), and to statutory grants of ultimate authority to the Attorney General. See 8 U.S.C. § 1227 (a) (“Any alien ... in and admitted to the United States shall, upon the order of the Attorney General, be removed if the alien is within one or more of the following classes of deportable aliens.”). The current INA, however, spells out the manner in which the Attorney General is to exercise his authority to order aliens removed, namely, through proceedings instigated by the INS before immigration judges, resulting in removal orders issued, after a full hearing, by one of those judges. There is therefore no tension between § 1227(a) and 8 U.S.C. § 1101 (a)(47)(A), and both can be given effect.

Unlike a claimed due process violation, a component of which is to show prejudice, see Ramirez-Alejandre, 320 F.3d at 872 , the BIA’s lack of authority to enter Noriega-Lopez’s removal .order renders that component of his proceedings “in essence, a legal nullity.” See Reynaga v. Cammisa, 971 F.2d 414, 417 (9th Cir.1992). We conclude that the relief the INS requested from the BIA was precisely the relief to which it was entitled once the BIA overturned the IJ’s decision terminating the proceedings — a remand to the IJ for further proceedings. Since the BIA act ed beyond its authority in deciding ■ sua sponte to enter a removal order for Noriega-Lopez, we reverse the denial of his habeas petition in part and remand for proceedings consistent with this opinion.

Each party shall bear its own costs.

AFFIRMED in part, REVERSED in part, and REMANDED.

. To support its conclusion, the BIA noted that the conviction document was "seen by an immigration officer in Stockton and he signed it and swore that it was a certified true copy of the original document. The case number on the order matches that written on the criminal complaint.” . Collateral consequences would attach if Noriega-Lopez’s removal order were upheld. As an aggravated felon, he would be inadmissible for twenty years. See 8 U.S.C. § 118 2 (a)(9) (A)(ii). . 8 U.S.C. § 1252 (a)(2)(C) provides that: "Notwithstanding any other provision of law, no court shall have jurisdiction to review any final order of removal against an alien who is removable by reason of having committed a criminal offense covered in [INA] section 212(a)(2) or 237(a)(2)(A)(iii), (B), (C), or (D)....” . We have not addressed the applicability of 8 U.S.C. § 1252 (d)(1) to habeas petitions. The Second Circuit recently commented, in a case considering the pre-IIRIRA INA's statutory exhaustion requirement, see 8 U.S.C. § 1105a(c) (repealed 1996), that “in light of the Supreme Court's holding in [INS v. St. Cyr, 533 U.S. 289 , 121 S.Ct. 2271 , 150 L.Ed.2d 347 (2001) ], it is potentially an open question whether the exhaustion requirement of § 106(c) applies in a habeas proceeding.” Beharry v. Ashcroft, 329 F.3d 51 , 60 & n. 12 (2d Cir.2003). But see Sundar v. INS, 328 F.3d 1320, 1323-24 (11th Cir.2003) (holding with reference to St. Cyr that § 1252(d)(1) applies to habeas petitions). . While the BIA order at issue is one of removal, Noriega-Lopez was a resident alien lawfully admitted to the country. Because he is a controlled substance offender and aggravated felon, Noriega-Lopez is "deportable.” See 8 U.S.C. §§ 1227 (a)(2)(B)(i) ("Any alien who at any time after admission has been convicted of a violation of (or a conspiracy or attempt .to violate) any law or regulation of a State, the United States, or a foreign country relating to a controlled substance ... other than a single offense involving possession for one’s own use of 30 grams or less of marijuana, is deportable.”); 1227(a)(2)(A)(iii) ("Any alien who is convicted of an aggravated felony at any time after admission is deportable."). See also id. § 1229(a)(1) ("An immigration judge shall conduct proceedings for deciding the inadmissibility or deportability of an alien.... Unless otherwise specified in this chapter, a proceeding under this section shall be the sole and exclusive procedure for determining whether an alien may be ... removed from the United States.”) (emphasis added). Cf. IIRIRA § 309(d)(2), 110 Stat. at 3009-627 ("any reference in law to an order of removal shall be deemed to include a reference to an order of exclusion and deportation or an order of deportation”). For purposes of this case, consequently, the terms "order of removal” and "order of deportation” are interchangeable. . AEDPA’s explication of what an “order of deportation” is and from whom it originates filled a void, since the old INA did not include the term in its "Definitions” section. See 8 U.S.C. § 1101 (1995). . 8 C.F.R. § l.l(Z) (1996) explained that "[t]he term immigration judge means special inquiry officer and may be used interchangeably with the term special inquiry officer wherever it appears in this chapter.” . See AEDPA § 440, 110 Stat. at 1277; IIRI-RA § 306, 110 Stat. at 3009607-08. .By contrast, the pertinent pre-IIRIRA provision, repealed 8 U.S.C. § 1105a (1995), stated that: "Service of the petition to review shall be made upon the Attorney General of the United States and upon the official of the Immigration and Naturalization Service in charge of the Service district in which the office of the clerk of the [federal appellate] court is located.” . Our holding is limited to those cases in which the INS successfully appeals an IJ's determination that an alien is not removable and therefore terminates proceedings. We leave for another day situations in which an IJ determines that an alien is removable (whether based on a concession or after adjudication) but grants relief from removal, and the BIA then rejects the grant of relief. . We note that this language is no longer part of the regulation cited by the INS. See 8 C.F.R. § 1003.1 (d)(1) ("The Board shall function as an appellate body charged with the review of those administrative adjudications under the Act that the Attorney General may by regulation assign to it. The Board shall resolve the questions before it in a manner that is timely, impartial, and consistent with the Act and regulations.”). . We express no opinion concerning whether on remand Noriega-Lopez may apply for relief before the IJ. We leave that question to the IJ in the first instance. See INS v. Ventura, 537 U.S. 12 , 123 S.Ct. 353, 355-56 , 154 L.Ed.2d 272 (2002) (listing advantages of “the law’s ordinary remand requirement,” which allows an agency to make an informed initial determination that can "help a court later determine whether [the agency's] decision exceeds the leeway that the law provides”).