This case raises issues of first impression in immigration law as to the validity of a regulation promulgated in 1997 by the Attorney General, 8 C.F.R. § 245.1(e)(8). The regulation redefines certain aliens as ineligible to apply for adjustment of status to lawful permanent residents whom a statute, 8 U.S.C. § 1255(a), defines as eligible to apply. Under that regulation, the Attorney General will not consider an application for adjustment of status from the entire category of aliens who have been granted parole status but have been placed in removal proceedings.
The essence of the Attorney General’s argument is that since he has been given ultimate discretion to deny adjustment of status after application, the validity of the regulation is itself not subject to judicial review, and, if it were, the regulation must be upheld as a permissible exercise of that ultimate discretion. We disagree on both points. We hold that there is no statutory bar to review and that the regulation is contrary to the language and intent of the statute, 8 U.S.C. § 1255(a). As a result, *10we vacate the order removing Wissam Succar from the United States and remand for further proceedings.
Our reasons, which we explain in more depth below, are as follows. The mere fact that a statute gives the Attorney General discretion as to whether to grant relief after application does not by itself give the Attorney General the discretion to define eligibility for such relief. That is clear from INS v. Cardoza-Fonseca, 480 U.S. 421, 443, 107 S.Ct. 1207, 94 L.Ed.2d 434 (1987). Courts must still interpret the statute. Where the statute is silent on eligibility, the agency involved may reasonably choose to exercise its discretion to withhold relief by excluding certain persons from eligibility for such relief. Lopez v. Davis, 531 U.S. 230, 121 S.Ct. 714, 148 L.Ed.2d 635 (2001).
Here, the statute is not silent — it defines persons who have parole status as eligible for adjustment of status and does not carve out an exception for parolees who are in removal proceedings. See 8 U.S.C. § 1255. That lack of a carve out for parolees in removal proceedings is itself significant, given that the statute contains a number of carve outs as to eligibility for adjustment of status. Some carve outs exclude persons from eligibility to apply who'would otherwise meet more general eligibility requirements. Further, other carve outs create eligibility in persons otherwise ineligible. Congress thus has created a comprehensive scheme.
' Viewing the larger statutory context, we find Congress has also been explicit about where the Attorney General has been granted discretion and where he has not. By contrast with other areas, there is no explicit grant of discretion to redefine eligibility to apply for adjustment of status of parolees to exclude those in removal proceedings. Congress did not place the decision as to which applicants for admission are placed in removal proceedings into the discretion of the Attorney General, but created mandatory criteria. See 8 U.S.C. §§ 1225(b)(1), (2). In addition, persons cannot be granted paroled status at all if they pose a security risk; they are to be ordered removed and this order must be reported to the Attorney General. 8 U.S.C. § 1255(c)(1).
The statutory scheme reflects Congress’s careful balancing of the country’s security néeds against the national interests Congress wished to advance through adjustment of status proceedings. The regulation upsets the balance Congress created.
Checking our construction of the statute against the legislative history of section 1255, we find the regulation to be inconsistent with the intent expressed in the statute. In 1960, when Congress included paroled aliens as aliens who are eligible for adjustment of status relief through section 1255, it did so to solve certain problems, which we describe later. The effect of the regulation is to re-institute the problems Congress wished to solve. Further, until the 1997 promulgation of the regulation, the Attorney General had consistently interpreted section 1255 in a manner consistent with the statute and the legislative history and inconsistent with the 1997 regulation.
In response to the Attorney General’s argument that the 1996 enactment of the Illegal Immigration Reform and Immigrant Responsibility Act (IIRIRA) justifies the 1997 regulation, we note the Attorney General’s concession that IIRIRA, which altered so much of the immigration laws, left untouched the language of section 1255, as enacted in 1960, on the matter in question. That being so, the relevance of the Attorney General’s remaining arguments, largely based on general policy said to be embodied in IIRIRA, is doubtful. *11To the contrary, IIRIRA tends to strengthen, not weaken, the petitioner’s claim that the regulation is invalid. Finally, the purported policy justifications of expediting removal of aliens and administrative ease must give way to clear congressional intent.
I.
Wissam Succar is a native and citizen of Lebanon. Succar arrived at Miami International Airport on October 21, 1998, when his flight from Lebanon to Panama stopped in the United States. He approached an official at the airport, stating that he wished to apply for asylum.
An immigration officer questioned Suc-car at the airport. Because Succar did not have the proper documentation for admission, he was taken into government custody and held at the Krome detention facility in Miami, Florida. An asylum pre-screen-ing officer met with Succar on November 19, 1998, and determined that he had a credible fear of persecution based on his involvement with the Christian militias in Lebanon. The officer found that the facts as recounted by Succar could establish his eligibility for asylum and a credible fear of harm on the basis of an imputed political opinion. Succar was placed into removal proceedings and was subsequently paroled into the United States on November 30, 1998. Succar has remained in parole status.
Over one year later, on January 19, 2000, Succar admitted the allegations in the Notice to Appear and conceded remov-ability; he renewed his application for asylum, withholding of removal, and protection under the Convention Against Torture. On March 1, 2000, a hearing was held on his asylum application and the trial was set for April 18, 2000. On April 18, after a hearing on the merits of his application, the Immigration Judge (IJ) denied Succar’s request for asylum and withholding of removal. Succar appealed this decision to the Board of Immigration Appeals (BIA).
On February 19, 2001, while his appeal was pending before the BIA and while he was paroled into the United States, Succar married a United States citizen. Succar’s wife filed an immigrant visa petition for him, and the petition was approved on April 26, 2001. The approval form directed Succar to contact the local INS office to obtain Form 1-485, the application for adjustment of status to a permanent resident. Believing that he met the statutory eligibility requirements for adjustment of status, on October 17, 2001, Succar filed a motion with the BIA to remand the proceedings to the IJ for consideration of his application for adjustment of status under 8 U.S.C. § 1255(a). This motion was unopposed by the INS.1 The BIA granted the motion on December 18, 2001 and remanded the case to the IJ for further proceedings. The remand proved to be fruitless for the INS soon took the position that under 8 C.F.R. § 245.1,2 Succar was ineligible to apply for adjustment of status either before the IJ in the removal proceedings or, separately, before the Immigration Service’s district director.
*12At a July 29, 2002 hearing, Succar submitted his adjustment of status application to the IJ. In the middle of the hearing, the IJ stated that based on 8 C.F.R. § 245.1, “I am confident that I don’t have the authority to adjust status to someone who’s an arriving alien.” The IJ denied the adjustment of status application as a matter of law, and then continued, “The Immigration Service doesn’t have the authority to adjust his status unless they are willing to terminate this case with me and if that be the case, I’ll happily do it but I don’t have the authority to terminate.In his oral decision of the same day, the IJ stated:
The respondent is an arriving alien and, therefore, he is not eligible to adjust status before the Immigration Judge. Additionally the respondent is not eligible to adjust status before the District Director of the Immigration Service in that he is in [removal] proceedings. As I indicated to both counsel, if the Immigration Service wished to have me terminate these proceedings or even to conditionally terminate them, I would have done so in order to afford the Immigration Service an opportunity to see whether an adjustment of status ought to be granted. However, that was not agreed to by the Immigration Service counsel.
The regulations provide under 8 C.F.R. Section 245.1(c)(8) that any arriving alien who is in removal proceedings pursuant to Section 235(b)(1) or Section 240 of the Act is ineligible to adjust status.
The IJ also reaffirmed the previous order of removal to Lebanon.
The petitioner appealed both parts of the IJ’s decision to the BIA, and on September 24, 2003, the BIA affirmed the IJ’s determination in full. On the adjustment of status issue, the BIA concurred with the IJ that Succar was “ineligible for adjustment of status because he is an “arriving alien.”3 Succar timely appealed the BIA’s decision to this court.
II.
We set the issues in the broader context of the requirements of immigration law.
A. Classes of Aliens
Before 1996, non-citizens were divided into two categories: (a) applicants for admission and (b) non-citizens present in the United States who had previously made an entry into the country either with, or without, an inspection. An applicant for admission, also called an arriving alien, was an individual seeking admission who had not yet entered the country.4 After an inspection, if an applicant was not admitted, he or she was subject to an exclusion proceeding to determine admissibility into the United States. The second category, non-citizens who had previously made an entry, were treated as being present in the *13United States. They were subject to deportation proceedings to determine whether they would be deported or admitted to stay.
In 1996, Congress passed IIRIRA. See generally Reno v. American-Arab Anti-Discrimination Comm., 525 U.S. 471, 119 S.Ct. 936, 142 L.Ed.2d 940 (1999); Goncalves v. Reno, 144 F.3d 110 (1st Cir.1998). Among many other changes, Congress eliminated the definition of the term “entry” and replaced it with the terms “admission” and “admitted.” See IIRIRA, Pub.L. No. 104-208, 110 Stat. 3009-575 (1996). Admission and admitted now include only “the lawful entry of the alien into the United States after inspection and authorization by an immigration officer.” 8 U.S.C. § 1101(a)(13)(A)(emphasis added). The main impact of this change is to re-characterize aliens who are present in the United States, but who have not been inspected and admitted. They are now considered “applicants for admission” along with other arriving aliens. The statute requires that all aliens who are seeking admission or readmission to the United States be inspected by immigration officers, prior to a determination of their status. See 8 U.S.C. § 1225(a)(3).
Congress also eliminated deportation and exclusion proceedings and replaced them with removal proceedings, which were applicable to all aliens who were (1) in the United States without an inspection, (2) inspected and not admitted, or (3) previously admitted but now subject to removal. See 8 U.S.C. §§ 1225(b)(2), 1227(a). Special removal proceedings were established for two types of individuals arriving in the United States: those who are (1) suspected of being terrorists or a security threat, 8 U.S.C. § 1225(c), or (2) stowaways, 8 U.S.C. § 1225(a)(2). Congress established expedited removal proceedings for arriving non-citizens who are charged as inadmissible due to lack of proper documents or material misrepresentations at entry. See 8 U.S.C. § 1225(b)(1). Expedited removal proceedings provide little opportunity for relief; however, aliens in this situation can seek asylum. See 8 U.S.C. § 1225(b)(1)(A). If the alien alleges a credible fear based on one of the statutory grounds, she receives an interview with an asylum pre-screening officer. If the officer finds that she has alleged facts sufficient to justify a credible fear, then the alien will be referred to an immigration judge. 8 C.F.R. § 235.3(b)(4); 8 C.F.R. § 235.6(a)(l)(ii).
The last type of proceeding is the standard removal proceeding for persons present in the United States, regardless of whether they are applicants for admission or have been living in the United States previously. 8 U.S.C. § 1225(b)(2); 8 U.S.C. § 1229a. Congress did not restrict the type of relief available to individuals in removal proceedings under section 1229a. Significantly, the statute does not by its terms prevent this class of individuals from applying for adjustment of status.
B. Adjtistment of Status
Adjustment of status is “a technical term describing a process whereby certain aliens physically present in the United States may obtain permanent resident status ... without leaving the United States.” 3B Am.Jur.2d Aliens & Citizens § 2134. Before 1960, adjustment of status in the United States was only available to non-citizens legally in the country. See Immigration and Nationality Act, Pub.L. No. 414, 66 Stat. 217 (1952)(INA). Any immigrant present in the United States who was eligible for adjustment of status, but who was no longer in valid immigration status, had to obtain an immigrant visa at a United States post abroad in order to obtain permanent resident status. See *14S.Rep. No. 86-1651 (1960), reprinted in 1960 U.S.C.C.A.N. 3124, 3136. To process the immigrant visa at the consular post abroad, an immigrant residing in the United States had to apply to the INS for preexamination and voluntary departure in order to insure that he would be able to be readmitted into the country once he obtained the immigrant visa. See id.
In 1960, Congress established the current procedure for adjustment of status to obviate the need for departure and reentry for aliens temporarily in the United States. Congress explicitly expanded the group of individuals eligible for adjustment of status to include all aliens who have been “inspected and admitted or paroled.” See Joint Resolution of July 14, 1960, Pub.L. No. 86-648, 74 Stat. 505 (codified as amended at 8 U.S.C. § 1255(a)) (“The status of an alien ... who was inspected and admitted or pa/roled into the United States may be adjusted by the Attorney General, in his discretion and under such regulations as he may prescribe, to that of an alien lawfully admitted for permanent residence ....”) (emphasis added).
“Admitted aliens” means individuals who have presented themselves for inspection by an immigration officer and who have been allowed to enter the country. See 8 U.S.C. § 1101(a)(13)(A). “Paroled aliens” are otherwise inadmissible aliens who are given permission by the Attorney General to enter temporarily. 8 U.S.C. § 1182(d)(5)(A). The statute governing parole states:
The Attorney General may, except as provided in subparagraph (B) or in section 1184(f) of this title, in his discretion parole into the United States temporarily under such conditions as he may prescribe only on a case-by-ease basis for urgent humanitarian reasons or significant public benefit any alien applying for admission to the United States.... 5
8 U.S.C. § 1182(d)(5)(A).
In addition to being “inspected and admitted or paroled,” aliens must be eligible to receive an immigrant visa and this visa must be immediately available to them. 8 U.S.C. § 1255(a). Aliens seeking an immigrant visa must first receive approval of an immigrant petition, which is usually filed by an employer or a relative. The alien must then wait for and receive an immigrant visa number, which means that a visa has been assigned.6 Dep’t of Home*15land Sec., Citizenship & Immigration Servs., How do I get an Immigrant Visa Number, at http://uscis.gov/graphics/how-doi/ immvisa.htm (last modified October 31, 2003).
C. Parole
The purpose of parole is to permit a non-citizen to enter the United States temporarily while investigation of eligibility for admission takes place.7 Congress has ordered certain aliens removed; they are not eligible for parole. 8 U.S.C. § 1225(c)(1). Congress has set forth the conditions for parole in the statute. See 8 U.S.C. § 1182(d)(5)(A). Congress authorizes the Attorney General to allow parole “temporarily under such conditions as he may prescribe only on a case-by-case basis for urgent humanitarian reasons or significant public benefit.” 8 U.S.C. § 1182(d)(5)(A). Accordingly, the Attorney General has promulgated regulations. 8 C.F.R. § 212.5. Under the regulations, aliens in one of five groups can be paroled for urgent humanitarian reasons or significant public benefit “provided the aliens present neither a security risk nor a risk of absconding.” 8 C.F.R. § 212.5(b). These five groups are: (1) aliens with a serious medical condition, (2) women who have been medically certified as pregnant, (3) aliens who are defined as juveniles in certain circumstances, (4) aliens who will be witnesses in judicial proceedings, and (5) aliens whose continued detention is not in the public interest as determined by the officials charged with exercising this discretion. 8 C.F.R. § 212.5(b)(l)-(5). In making their decisions, immigration officers can consider whether the alien has “[cjommunity ties” such as close relatives with known addresses. 8 C.F.R. § 212.5(d)(2). Arriving aliens who claim asylum and establish a credible fear with an asylum pre-screening officer can be paroled at the point of entry while they pursue their asylum application.8
A paroled individual is not considered “admitted” into the United States: he is an “applicant for admission.” 8 U.S.C. § 1101(13)(B). He is not detained and is allowed to temporarily enter the United *16States. However, “when the purposes of such parole ... have been served the alien shall forthwith return or be returned to the custody from which he was paroled and thereafter his case shall continue to be dealt with in the same manner as that of any other applicant for admission to the United States.” 8 U.S.C. § 1182(d)(5)(A). It appears from the face of the statute that the Attorney General has no discretion in this determination. As soon as the reasons for parole have been served, the individual must be returned to custody.
By statute, paroled individuals9 are eligible for adjustment, of status if they meet the other statutory eligibility requirements. 8 U.S.C. § 1255(a). Section 1255 makes no distinction between those who are in removal proceedings and those who are not for purposes of adjustment of status.
Since the 1960 enactment of section 1255(a), Congress has on several occasions amended other provisions of 8 U.S.C. § 1255 to restrict the class of people who are eligible to receive adjustment of status. For example, alien crewmen, aliens continuing or accepting unauthorized employment, and aliens admitted in transit without a visa are not eligible to adjust status under section 1255(a), unless they fall into limited exceptions to the bar on eligibility. 8 U.S.C. § 1255(c). Congress also limited the ability of an alien to adjust status if the alien is married in the United States while in judicial -proceedings. 8 U.S.C. § 1255(e)(1).10 Significantly, Congress has never taken parolees, as a group, out of the class of eligible aliens, despite over a dozen opportunities — where section 1255 was otherwise amended — to do so.
Parolees, although they are physically present in the United States, are treated as if they were at the border seeking admission. Before the 1996 IIRIRA statutory changes, parolees were subject to exclusion proceedings. Post-IIRIRA, individuals who are paroled and are seeking asylum are subject to removal proceedings. As arriving aliens, parolees are subject to removal proceedings. “[I]f the examining officer determines that an alien seeking admission is not clearly and beyond a doubt entitled to be admitted, the alien shall be detained for a [removal] proceeding-” 8 U.S.C. § 1225(b)(2)(A). Parolees are generally not “clearly and beyond a doubt” entitled to admission. However, as parolees, they are not in detention. Until the final order of removal, which in some circumstances — such as where the applicant is applying for asylum — can take years, paroled aliens in removal proceedings, such as Succar, live, work and form relationships within the United States.
D. Parolees and Adjustment of Status
Before the promulgation of 8 C.F.R. § 245.1(c)(8), paroled aliens in exclusion proceedings had an independent avenue to apply for adjustment of status.11 In re *17Castro-Padron, 21 I. & N. Dec. 379, 379-80, 1996 WL 379828 (BIA 1996). The BIA held that in exclusion proceedings, jurisdiction over an alien’s application for adjustment of status lay with the district director of the immigration agency, not the IJ. Id. at 379. The Board explained, “[Ajpplicants [in exclusion proceedings] can file their adjustment application with the district director of the [INS], who has sole jurisdiction over the application and can act on the application independently of these [exclusion] proceedings.” Id. at 380.
Historically, the district director had jurisdiction over the adjustment application of both aliens in deportation proceedings who were admitted and aliens in exclusion proceedings who were paroled.12 In re Manneh, 16 I. & N. Dec. 272, 274, 1977 WL 39268 (BIA 1977). In 1961, regulations gave the IJ the authority in deportation cases to renew admitted aliens’ adjustment applications that were denied by the district director and to adjudicate initial applications for such aliens in deportation proceedings. Id. With this change, the district director no longer had authority over adjustment applications once deportation proceedings began. Id. However, the Board determined that this enlarged jurisdiction did not apply when the alien was in exclusion proceedings: the district director retained sole authority for adjustment of status applications. Id.
In 1997, the Attorney General13 promulgated new regulations, which were said to implement IIRIRA. The regulations created a new definition for the term arriving alien:
The term arriving alien means an applicant for admission coming or attempting to come into the United States at a port of entry, or an alien seeking transit through the United States at a port-of-entry, or an alien interdicted in international or United States waters and brought into the United States by any means, whether or not to a designated port-of-entry, and regardless of the means of transport. An arriving alien remains such even if paroled pursuant to section 212(d)(5) of the Act....
8 C.F.R. § l.l(q).
Armed with this new definition of arriving alien, the Attorney General made a substantive change to the adjustment of status regulations. The Attorney General made several categories of aliens ineligible to apply for adjustment of status under 8 U.S.C. § 1255(a), including “[a]ny arriving alien who is in removal 'proceedings pursuant to section 235(b)(1) or section 240 of the Act.” 8 C.F.R. § 245.1(c)(8) (emphasis added). It is this particular provision of *18the regulation that is challenged before this court.
The Attorney General also enacted regulations regarding the proper place for an eligible individual to file for adjustment of status. A key regulation states:
An alien [who believes he or she is eligible for adjustment of status] shall apply to the director having jurisdiction over his or her place of residence.... After an alien, other than an arriving alien, is in deportation or removal proceedings, his or her application for adjustment of status ... shall be made and considered only in those proceedings.... An arriving alien, other than an alien in removal proceedings, who believes he or she meets the eligibility requirements ..., shall apply to the director having jurisdiction over his or her place of arrival.
8 C.F.R. § 245.2(a)(1) (emphasis added). A parolee in removal proceedings thus no longer has the ability to apply before anyone, either the district director or the IJ, for adjustment of status. By contrast, a parolee who is not in removal proceedings (as an arriving alien) can, consistent with earlier practice, apply to the district director for adjustment of status. .We are informed that most arriving alien parolees are placed in removal proceedings. The new regulatory scheme is, thus, a break from earlier practice.
In promulgating 8 C.F.R. § 245.1(c)(8) in 1997, the Attorney General explained the rationale for the hew regulation:
Consistent with Congress’ intent that arriving aliens ... be removed in an expedited manner through the procedures provided ..., the Attorney General has determined that she will not favorably exercise her discretion to adjust the status of arriving aliens who are ordered removed....
62 Fed.Reg. 444, 452 (January 3, 1997). In an effort to quickly remove aliens, the regulation aimed to eliminate avenues available to arriving aliens in removal proceedings that allow such aliens to “delay their removal through an application for adjustment of status.” Id. The Attorney General explained that an arriving alien will not be able to adjust status within the United States. If an arriving alien is eligible for an immigrant visa, she will be “required to return to ... her country of residence and request it through the consular process available to all aliens outside of the United States.” Id. The Attorney General believed that if “the Service decides as a matter of prosecutorial discretion, not to initiate removal proceedings but to parole the arriving alien, the alien will.be able to apply for adjustment of status before the district director.” Id.
Under the new regulations, arriving aliens in removal proceedings (regardless of whether they otherwise meet the statutory criteria for adjustment of status) must leave the United States and go through consular processing in order to adjust status; the respondent has represented that this is the only option available to them. But there are significant limitations even as to this avenue. Non-citizens are subject to -8 U.S.C. § 1182(a)(9)(B)(i), which bars non-citizens from reentry into the United States for three years if they were unlawfully present in the United States for more than 180 days but less than one year and for ten years if they were unlawfully present for more than one year.14 Any waiver of this statutory bar is in the absolute discretion of the Attorney General. 8 U.S.C. § 1182(a)(9)(B)(v). Also, non-citizens who have not been admitted into the *19United States are ineligible for voluntary departure. 8 U.S.C. § 1229c(a)(4). Following any involuntary removal, they will be ineligible for readmission for five years unless the Attorney General grants a waiver. 8 U.S.C. § 1182(a)(9)(A)(i)f (in). Parolees have, by definition, not been admitted, and thus will generally be subject to this five year bar for involuntary removal as well. Denying paroled aliens in removal proceedings the ability to adjust status within the United States thus creates a significant hardship on these individuals and their families.
Of course, as the Attorney General has stated, the immigration agency in theory can decide to terminate the removal proceedings in the alien’s favor, which would allow the arriving alien — who would then not be in removal proceedings — to apply for adjustment of status before the district director. The government as prosecutor in the removal proceedings may, in its discretion, terminate the proceedings in order to permit the alien to apply for adjustment of status. But as this case demonstrates, the BIA has apparently taken the position that neither it nor the IJ may suspend or terminate the proceedings for this purpose without the government’s consent.
III.
Availability of Judicial Revieio of Statutory Interpretation Claim
The Attorney General first argues that 8 U.S.C § 1252(a)(2)(B) precludes judicial review of the Attorney General’s denial of Succar’s application for adjustment of status because the Attorney General, through the promulgation of 8 C.F.R. § 245.1(e)(8), made a discretionary determination that arriving aliens do not merit adjustment of status under 8 U.S.C. § 1255. We disagree and exercise review.
Section 1252 provides for judicial review of orders of removal, and sets forth limitations on this review. The Attorney General relies on § 1252(a)(2)(B), which reads in part as follows:
(B) Denials of discretionary relief
Notwithstanding any other provision of law, no court shall have jurisdiction to review—
(i) any judgment regarding the granting of relief under section ... 1255 of this title
8 U.S.C § 1252(a)(2)(B)(i). Both the Supreme Court and this court have consistently rejected arguments that Congress has eliminated judicial review of the legal question of interpretation of the statute as to whether an alien is eligible for consideration of relief.15
Succar challenges the Attorney General’s regulation as being contrary to the statute; that is a classic issue for the court to decide. The issue presented is a purely legal question and as such is not within the jurisdictional bar of 8 U.S.C. § 1252(a)(2)(B). That is the ruling of Zadvydas v. Davis, 533 U.S. 678, 688, 121 S.Ct. 2491, 150 L.Ed.2d 653 (2001), which exercised judicial review over a challenge to the extent of the Attorney General’s authority to detain an alien indefinitely under the post-removal-period detention statute because the authority of the Attorney General to act is “not a matter of *20discretion” and is subject to judicial review. So here the challenge goes to the Attorney General’s statutory authority and not his discretion. See Subhan v. Ashcroft, 383 F.3d 591, 594 (7th Cir.2004) (interpreting 8 U.S.C. § 1252(a)(2)(B) as preserving jurisdiction when the decision is not “a judgment denying a request for adjustment of status” under 8 U.S.C. § 1255); see also Montero-Martinez v. Ashcroft, 277 F.3d 1137, 1141 (9th Cir.2002) (Section 1252(a)(2)(B)(i) does not preclude, review of “purely legal and hence non-diseretionary” questions.); Prado v. Reno, 198 F.3d 286, 288 (1st Cir.1999) (Whether a court can exercise review depends on the grounds upon which the decision of the BIA rests and “the precise nature of the claims made in the petition.”).
Quite literally, the Attorney General did not, under 8 U.S.C. § 1252(a)(2)(B)(i), make “a judgment .regarding the granting of relief under section 1255,” because the effect of the regulation is to preclude an alien from even applying for relief under section 1255. See Subhan, 383 F.3d at 594 (exercising jurisdiction over the IJ’s decision even though the effect of the decision is the same as that of a denial of an adjustment of status application; the court has jurisdiction because “the purpose behind [8 U.S.C. § 1252(a)(2)(B)®] is presumably to shield from judicial review judgments regarding the propriety of adjusting an alien’s status, and no such judgment has ever been made with regard to the [petitioner]”).
This court has jurisdiction to review Succar’s claim under 28 U.S.C. § 1331, which grants courts general federal question jurisdiction, Reno v. Catholic Soc. Servs., Inc., 509 U.S. 43, 56, 113 S.Ct. 2485, 125 L.Ed.2d 38 (1993), and the Administrative Procedure Act (APA), which gives a court power to “ ‘hold unlawful and set aside’ not only agency action that is ‘arbitrary ’ or ‘capricious,’ but also agency action that is ‘otherwise not in accordance with law’ or is ‘in excess of statutory jurisdiction, authority, or limitations, or short of statutory right.’ ” Cousins v. Sec’y of the United States Dep’t of Transp., 880 F.2d 603, 608 (1st Cir.1989) (quoting 5 U.S.C. § 706(2)(A, C)). “It is ‘central to the real meaning of “the rule of law,” [and] not particularly controversial’ that a federal agency does not have the power to act unless Congress, by statute, has empowered it to do so.” Transohio Sav. Bank v. Dir., Office of Thrift Supervision, 967 F.2d 598, 621 (D.C.Cir.1992) (quoting Edward L. Rubin, Law and Legislation in the Administrative State, 89 Colum. L.Rev. 369, 402 (1989)) (alteration in Transohio). When an agency action is contrary to the scope pf a statutory delegation of authority or is an arbitrary and capricious exercise of that authority, that action must be invalidated by reviewing courts.
IV.
A. Merits: Validity of Regulation Vis-cu-Vis the Statute
The question presented is whether the regulation, 8 C.F.R. § 245.1(c)(8), is invalid as clearly contrary to 8 U.S.C. § 1255(a) or as an arbitrary or capricious exercise of the Attorney General’s delegated authority. The regulation affects certain arriving aliens who have been granted parole into the United States and have also been placed in removal proceedings. As explained above, before adoption of 8 C.F.R. § 245.1(c)(8) in 1997, this category of aliens, if they met the other statutory requirements, could apply for adjustment of status with the local district director. The effect of 8 C.F.R. § 245.1(c)(8) is to deny eligibility for relief under 8 U.S.C. § 1255 to this category of aliens by precluding consideration of their applications *21either before the district director or before an IJ.
Sucear and supporting amici16 launch a three-fold attack on the regulation. First, they argue the regulation is flatly inconsistent with congressional intent as expressed in 8 U.S.C. § 1255(a) and the legislative history. Alternatively, they argue there are two possible interpretations of the regulation which must be adopted to avoid a conflict between the regulation and the statute. Finally, they argue that the Attorney General has acted ultra vires. Suc-car argues that 8 U.S.C. § 1255(a) expressly mentions persons in parole status (without restricting that status to those not in removal proceedings) as among those eligible to apply for adjustment of status, and therefore Congress intends for any decision made within the Attorney General’s admitted discretion to be made on an individualized basis after an eligible alien applies, not as a categorical eligibility exclusion.17
The Attorney General defends the regulation, arguing that 8 U.S.C. § 1255(a) expressly states that the decision to grant adjustment of status is subject to the Attorney General’s discretion and that the regulation is no more than a valid exercise of that discretion. The Attorney General points out that the regulation does not make all of those in parole status ineligible to apply for adjustment of status, only those who have been placed in removal proceedings. However, it was represented in the briefs before this court that the “majority of the intended beneficiaries of parolee adjustment of status are in removal proceedings.” The Attorney General does not dispute this statement.
Paroled individuals must be placed in removal proceedings “if the examining immigration officer determines that an alien seeking admission is not clearly and beyond a doubt entitled to be admitted.” 8 U.S.C. § 1225(b)(2)(A). The Attorney General argues that the challenged regulation does not effectuate a final exclusion from eligibility because even though these individuals cannot apply while they are physically in the United States, the alien can leave the United States and then apply for an immigrant visa at the embassy or consular office in his home country.
The petitioner responds that the result of such a requirement, contrary to congressional intent, is that many aliens would be barred from even applying from outside the country for long periods of time because of the statutory bars discussed above. 8 U.S.C. § 1182(a)(9).18 As *22we shall see, in enacting section 1255(a) in 1960, Congress expressed an intent that eligible aliens be able to adjust status without having to leave the United States, to relieve the burden on the United States citizen with whom the aliens had the requisite family or other relationship, on the United States consulates abroad, and on the alien. That was one of the primary purposes of the legislation.
The Attorney General also argues that the passage of IIRIRA, Pub.L. No. 104-208, 110 Stat. 3009 (1996), altered the immigration laws in many restrictive ways. Petitioner counters that IIRIRA did indeed tighten restrictions, but points out that application for adjustment of status by parolees was one of the few areas untouched. This, the petitioner says, reflected Congress’s consistent understanding that the immigration agency would consider applications for adjustment of status from parolees, whether in removal proceedings or not.
B. Standard of Review
Two points are undisputed: Congress has granted the Attorney General some degree of discretion to adjust the status of statutorily specified aliens in 8 U.S.C. § 1255 and Congress has granted the Attorney General authority to promulgate regulations which guide the exercise of this discretion. 8 U.S.C. § 1103(g)(2). When there is no challenge to whether Congress authorized the Attorney General to issue regulations, we are faced with only two questions.
We first ask whether “Congress has directly spoken to the precise question at issue.” Chevron USA, Inc. v. Natural Res. Def. Council, Inc., 467 U.S. 837, 842, 104 S.Ct. 2778, 81 L.Ed.2d 694 (1984). If so, courts, as well as the agency, “must give effect to the unambiguously expressed intent of Congress.” Id. at 842-43. As the Supreme Court has said in the immigration context:
The judiciary is the final authority on issues of statutory construction and must reject administrative constructions which are contrary to clear congressional intent. If a court, employing traditional tools of statutory construction, ascertains that Congress had an intention on the precise question at issue, that intention is the law and must be given effect.
INS v. Cardoza-Fonseca, 480 U.S. at 447-48, 107 S.Ct. 1207 (quoting Chevron USA Inc., 467 U.S. at 843 n. 9, 104 S.Ct. 2778) (internal quotation marks omitted). “Chevron [] deference to [an agency’s] statutory interpretation is called for only when the devices of judicial construction have been tried and found to yield no clear sense of congressional intent.” Gen. Dynamics Land Sys., Inc. v. Cline, 540 U.S. 581, 124 S.Ct. 1236, 1248, 157 L.Ed.2d 1094 (2004).
In determining whether a statute exhibits Chevron-type ambiguity, and hence warrants deference to the Attorney General’s interpretation of the statute, courts look at both the most natural reading of the language and the consistency of the “interpretive clues” Congress provided. Gen. Dynamics Land Sys., Inc., 124 S.Ct. at 1240, 1248. In determining the meaning of a statute, our analysis begins with the language of the statute. See Leocal v. Ashcroft, — U.S.-, 125 S.Ct. 377, 382, 160 L.Ed.2d 271 (2004) (reversing INS interpretation of term “crime, of violence” in 8 U.S.C. § 1227(a)(2)(A)(iii) and 8 *23U.S.C. § 1101(a)(43)(f)). “[W]e construe language in its context and in light of the terms surrounding it.” Id. Another “regular interpretive method” is reference to statutory history to see if any “serious question ... even about purely textual ambiguity” is left. Gen. Dynamics Land Sys., Inc., 124 S.Ct. at 1248.
However, whenever Congress has left a gap for the agency to fill, then we reach the second question, for the agency’s regulation is “given controlling weight unless [it is] arbitrary, capricious, or manifestly contrary to the statute.” Chevron USA, Inc., 467 U.S. at 843-44, 104 S.Ct. 2778; see Household Credit Servs., Inc. v. Pfennig, 541 U.S. 232, 124 S.Ct. 1741, 1746-47, 158 L.Ed.2d 450 (2004).
If the statutory terms are ambiguous, then the principle of Chevron deference to the Attorney General’s choice must apply. Cardoza-Fonseca, 480 U.S. at 448, 107 S.Ct. 1207. Indeed, the Supreme Court has said that “judicial deference to the Executive Branch is especially appropriate in the immigration context where officials ‘exercise especially sensitive political functions that implicate questions of foreign relations.’ ” INS v. Aguirre-Aguirre, 526 U.S. 415, 425, 119 S.Ct. 1439, 143 L.Ed.2d 590 (1999) (quoting INS v. Abudu, 485 U.S. 94, 110, 108 S.Ct. 904, 99 L.Ed.2d 90 (1988)).19 That said, the court has not hesitated to reject an INS interpretation as contrary to congressional intent. See, e.g., Leocal, 125 S.Ct. at 382; Cardoza-Fonseca, 480 U.S. at 448-49, 107 S.Ct. 1207.
C. Statutory Ambiguity
Each party initially argues that the statute is unambiguous, in its favor. The Attorney General argqes that the statute unambiguously .grants him discretion to allow or deny adjustment of status to an alien. One way to exercise that discretion, the Attorney General argues, is to make certain categories of otherwise eligible aliens ineligible to apply and so ineligible to warrant the favorable exercise of the Attorney General’s discretion. In the Attorney General’s view, this is the end of the matter.
We agree that the statute gives the Attorney General discretion, but disagree that this ends the analysis as to whether the Attorney General can promulgate this particular categorical eligibility exclusion. The Supreme Court itself has ruled that the two questions of discretion as to the ultimate relief and discretion as to eligibility exclusions are distinct. See Cardoza-Fonseca, 480 U.S. at 443-44, 107 S.Ct. 1207 (distinguishing between the discretion in the Attorney General as to the ultimate decision to grant relief and the underlying process and criteria for eligibility for relief); see also Goncalves, 144 F.3d at 125 (“Analytically, the decision whether an alien is eligible to be considered for a particular discretionary form of relief is a statutory question separate from the dis*24cretionary component of the administrative decision whether to grant relief.”).
The statute, we find, is unambiguous on this issue and that congressional clarity works against the Attorney General. We reject the respondent’s argument that Congress authorized 8 C.F.R. § 245.1(c)(8), making parolees in removal proceedings ineligible to adjust status, either by “express delegation or the introduction of an interpretive gap.” Pauley v. BethEnergy Mines, Inc., 501 U.S. 680, 696, 111 S.Ct. 2524, 115 L.Ed.2d 604 (1991). Congress has spoken clearly on the issue of eligibility for adjustment of status and has reserved for itself the determination of whether a non-citizen should be able to apply for this relief. The Attorney General cannot promulgate a regulation that categorically excludes from application for adjustment of status a category of otherwise eligible aliens; this is contrary to congressional intent in section 1255.
1. Text of the Statute
We look first to 8 U.S.C. § 1255 itself, which provides:
§ 1255. Adjustment of status of nonim-migrant to that of person admitted for permanent residence
(a) Status as person admitted for permanent residence on application and eligibility for immigrant visa
The status of an alien who was inspected and admitted or paroled into the United States or the status of any other alien having an approved petition for classification ... may be adjusted by the Attorney General, in his discretion and under such regulations as he may prescribe, to that of an alien lawfully admitted for permanent residence if (1) the alien makes an .application for such adjustment, (2) the alien is eligible to receive an immigrant visa and is admissible to the United States for permanent residence, and (3) an immigrant visa is immediately available to him at the time his application is filed.
8 U.S.C. § 1255(a) (emphasis added).
Congress defined certain categories of aliens who were eligible to apply for adjustment of status, 8 U.S.C. § 1255(a), and refined the definition by specifically excluding certain aliens from eligibility, 8 U.S.C. §§ 1255(c), (e). By statute, two categories of aliens are eligible to apply. First is an alien who was inspected and admitted. Second is an alien who was paroled. 8 U.S.C. § 1255(a). The Attorney General’s regulation carves out an exception from this second category of eligible aliens, by making paroled aliens who are placed in removal proceedings ineligible for adjustment of status relief, even if they otherwise meet the statutory requirements. 8 C.F.R. § 245.1(c)(8).
Congress unambiguously reserved to itself the determination of who is eligible to apply for adjustment of status relief. 8 C.F.R. § 245.1(c)(8) conflicts with the statute in several ways.
First, Congress itself explicitly determined categories of aliens (those aliens who had been “inspected and admitted or paroled”) who are eligible for adjustment of status if they otherwise meet the statutory requirements. 8 U.S.C. § 1255(a). Despite numerous amendments to 8 U.S.C. § 1255 since 1960, Congress has not limited the eligibility of paroled aliens under section 1255(a).20 The statute has never *25stated that an alien is ineligible to adjust status if he is in removal proceedings.
Second, when Congress desired to limit the ability of a non-citizen who might otherwise have been eligible to apply for adjustment of status under 1255(a), it has done so explicitly by defining several categories of aliens as not eligible to apply. For example, alien crewmen, aliens continuing or accepting unauthorized employment, and aliens admitted in transit without a visa are not eligible to adjust status under section 1255(a) unless they fall into limited exceptions. 8 U.S.C. § 1255(c) (“[SJubsection (a) [of 8 U.S.C. § 1255] shall not be applicable to ... :”)(emphasis added); Another category of aliens that Congress has explicitly determined is ineligible to apply for relief under section 1255(a) is the alien who is seeking to obtain an immigrant visa based on a marriage entered into while judicial proceedings are pending regarding the alien’s right to be admitted or remain in the United States. 8 U.S.C. § 1255(e).21 The statute is clear that even if these individuals were “inspected and admitted or paroled” and complied with the other statutory requirements, they are not eligible to apply.
There are two themes. First, Congress explicitly rendered ineligible a certain category of aliens to apply. Second, that category of excluded aliens included some in removal proceedings, but Congress chose not to disqualify from eligibility all of those aliens “inspected and admitted or paroled” in removal or other judicial proceedings. In those limited circumstances when the involvement in proceedings works to hamper an individual’s ability to adjust status, Congress has explicitly said so.
Third, Congress also has determined that some aliens whom it has deemed ineligible under 8 U.S.C. § 1255(c) might in some limited circumstances still be eligible for adjustment of status relief. For example, in 8 U.S.C. § 1255(i), Congress allows adjustment of status for certain aliens who entered the United States without inspection or who are categorized in section 1255(c) of the statute as being ineligible. Congress states that if these aliens are beneficiaries of either “(i) a petition for classification under [8 U.S.C. § ] 1154 ... that was filed with the Attorney General on or before April 30, 2001; or (ii) an application for a labor certification under [8 U.S.C. § ] 1182(a)(5)(A) ... that was filed ... on or before such date,” then they “may apply to the Attorney General for adjustment of ... status to that of an alien lawfully admitted for permanent residence.” See 8 U.S.C. § 1255(i).22 When *26Congress has wanted to impose special restrictions on the applications for certain categories of aliens that it has deemed eligible, or conversely to open up eligibility for aliens that were ineligible, it has done so explicitly. But Congress has imposed no restrictions on applying for adjustment of status for a paroled alien based on that alien’s being in removal proceedings.
2. Context of the Statutory Scheme
The terms and provisions of 8 U.S.C. § 1255(a) must be understood in the larger context of the statutory scheme. The immigration laws about adjustment of status are not a haphazard compilation of provisions; they are a calibrated set of rules that govern an area of national importance. Congress in many instances has specifically determined when to give discretion to the Attorney General and when to make its own policy choices. Viewing the statutory scheme in this manner clarifies two things: first, that the exclusion of parolees in removal proceedings renders ineligible most of the class that Congress rendered eligible by including parolees (for Congress clearly stated that most parolees would be in removal proceedings), and second, that the congressional choice to delegate to the Attorney General some circumscribed discretion over the ultimate decision of who is granted adjustment of status23 is not authorization for discretion in other areas.
We explain: one policy choice Congress made was to allow (in some instances) aliens who were otherwise inadmissible on arrival the opportunity to seek adjustment of status relief if they met certain statutory criteria. See 8 U.S.C. § 1255. In 8 U.S.C. § 1182, Congress defines the classes of aliens who are ineligible for visas or admission to the United States and makes various exceptions from these blanket rules. See 8 U.S.C. § 1182(a). Congress also allows for parole of these inadmissible aliens for “urgent humanitarian reasons” or “significant public benefit.” 8 U.S.C. § 1182(d)(5)(A). Congress specifically says parolees are not considered admitted. Id. Despite their status as inadmissible, Congress has also made the policy determination that these paroled aliens should be eligible to apply for adjustment of status, which essentially can act as an admission. 8 U.S.C. § 1255(a).
Section 1182 is integral to determinations made in “inspection,” which is provided for in 8 U.S.C. § 1225. All arriving aliens and aliens who are present in the United States without an inspection are *27“applicants for admission,” 8 U.S.C. § 1225(a)(1), and they “shall be inspected.” 8 U.S.C. § 1225(a)(3) (emphasis added). Section 1225(b) provides for-the inspection of aliens arriving in the United States and certain other aliens who have not been admitted or paroled. See 8 U.S.C. § 1225(b). If aliens being inspected are not “clearly and beyond a doubt”, admissible, under section 1182, then they must be referred to removal proceedings. See 8 U.S.C. § 1225(b)(2)(A).
This context shows that Congress purposefully classified paroled individuals as “inadmissible,” and it also determined that they should generally be placed in removal proceedings. But Congress also explicitly allowed paroled indiyiduals to adjust status if they meet the other statutory requirements.
Further, the larger statutory scheme makes clear that in the context of adjustment of status, Congress is particular about where it grants “discretion” to the Attorney General. Congress has specified the conditions under which an arriving alien (including a paroled alien) is to be determined inadmissible and must be placed in removal proceedings. The determination as to placing an alien into removal is not a decision committed to agency discretion by Congress. Rather, Congress has defined the terms for initiating removal proceedings against arriving aliens in 8 U.S.C. § 1225(b)(2)(A), which provides that, . '
[I]n the case of an alien who is an applicant for admission, if the examining immigration officer determines that an alien seeking admission is not clearly and. beyond a doubt entitled to be admitted, the alien shall be detained for a [removal proceeding],
8 U.S.C. § 1225(b)(2)(A). Congress used the word “shall” to mandate that an immigration officer who cannot determine that the applicant for admission is clearly entitled to be admitted has no choice but to place the alien in removal proceedings. After the alien is placed in removal, the Attorney General may parole the alien into the United States in some instances,24 but the alien still must go through removal proceedings.25
The incorrectness of the Attorney General’s argument can be seen by looking at one of its logical implications. The Attorney General is also given discretion as to the ultimate decision in determining whether to grant asylum to aliens who are eligible for this relief. 8 U.S.C. § 1158(a); Cardoza-Fonseca, 480 U.S. at 443-44, 107 *28S.Ct. 1207.26 If this grant of discretion meant what the government argues here, it would be logical that the Attorney General could similarly decline to allow asylum by issuing a regulation that refused to process applications from categories of asylum applicants.
But that is not so. If the asylum applicant meets the eligibility requirements — -if, in other words, the Attorney General determines that an applicant for asylum establishes she has “a well founded fear of persecution” on account of one of the statutory grounds — the alien must be allowed to apply. The Attorney General may only exercise his discretion in granting the asylum.27 8 U.S.C. § 1158(b); 8 U.S.C. § 1101(a)(42)(A). Similarly, if the paroled adjustment of status applicant meets the eligibility requirements, the Attorney General may exercise his discretion only in the decision whether to grant permanent resident status. In both asylum and adjustment of status, an alien who satisfies the eligibility requirements to apply “does not have a right to the [relief],” but he is “eligible” to apply for it. Cardoza-Fonseca, 480 U.S. at 443-44, 107 S.Ct. 1207 (emphasis removed).
Although the regulation, 8 C.F.R. § 245.1(c)(8), denying adjustment of status to parolees in removal proceedings is itself framed in terms of who is eligible to apply, the Attorney General argues the regulation is simply a determination at the outset that of the eligible parolees, the Attorney General will not exercise its discretion favorably to those who are in removal proceedings. The Attorney General relies on Lopez v. Davis, 531 U.S. 230, 121 S.Ct. 714, 148 L.Ed.2d 635 (2001), for the proposition that categorically excluding otherwise eligible individuals is an appropriate use of his discretion as to the ultimate decision granted in 8 U.S.C. § 1255(a).
Lopez is distinguishable. In Lopez, the Supreme Court upheld a regulation of the Bureau of Prisons (BOP), 28 C.F.R. § 550.58(a)(l)(vi)(B), which categorically denied early release to prisoners whose current offense was a drug felony involving the carrying, possession, or use of a firearm. See Lopez, 531 U.S. at 233, 121 S.Ct. 714. The relevant statute states, “The period a prisoner convicted of a nonviolent offense remains in custody after successfully completing a treatment program may be reduced by the [BOP], but such reduction may not be more than one year from *29the term the prisoner must otherwise serve.” 18 U.S.C. § 3621(e)(2)(B). The Supreme Court framed the question as whether “the Bureau has discretion to delineate, as an additional category of ineligible inmates, those whose current offense is a felony involving a firearm.” Lopez, 531 U.S. at 238, 121 S.Ct. 714. The Court answered this question in the affirmative, agreeing with the BOP that “Congress simply did not address how the Bureau should exercise its discretion within the class of inmates who satisfy the. statutory prerequisites for early release.” Id. at 239-40, 121 S.Ct. 714 (internal quotation marks omitted). The Court noted:
Beyond instructing that the Bureau has discretion to reduce the period of imprisonment for a nonviolent offender who successfully completes drug treatment, Congress has not identified any further circumstance in which the Bureau either must grant the reduction, or is forbidden to do so. In this familiar situation, where Congress has enacted a law that does not answer “the precise question at issue,” all we must decide is whether the Bureau, the agency empowered to administer the early release program, has filled the statutory gap “in a way that is reasonable in light of the legislature’s revealed design.”
Id. at 242, 121 S.Ct. 714 (emphasis added)(quoting NationsBank of N.C., N.A. v. Variable Annuity Life Ins. Co., 513 U.S. 251, 257, 115 S.Ct. 810, 130 L.Ed.2d 740 (1995)). In the face of congressional silence, the Court held that it was not unreasonable for the BOP to exercise its discretion and exclude a class of prisoners as ineligible for early release. Id. at 242-43, 121 S.Ct. 714.
By contrast, Congress has not been silent here. There are differences in the two statutes. In the adjustment of status statute here, Congress made numerous and explicit policy choices about who is eligible for adjustment of status relief, who is ineligible, and of those ineligible, who is nonetheless . eligible with certain application restrictions. See 8 U.S.C. § 1255(a) (setting out basic eligibility requirements for adjustment of status); 8 U.S.C. §§ 1255(c), (e) (limiting the , eligibility of otherwise . eligible aliens); 8 U.S.C. § 1255(i) (allowing eligibility to otherwise ineligible aliens). The statutory immigration scheme also constrains the Attorney General’s discretion in several ways, including mandating when an arriving alien must be placed in removal proceedings, 8 U.S.C. § 1225(b)(2)(A), limiting the discretion of the Attorney General to parole aliens, 8 U.S.C. § 1182(d)(5), and denying the Attorney General the ultimate discretion to adjust the status of some otherwise eligible aliens, 8 U.S.C. § 1255(f). Lopez is a Chevron step two case because of congressional silence; our case, however, is a Chevron step one case because Congress has clearly spoken on the issue of eligibility. We find the Attorney General’s regulation to be inconsistent with that congressional determination. See Ragsdale v. Wolverine World Wide, Inc., 535 U.S. 81, 91, 122 S.Ct. 1155, 152 L.Ed.2d 167 (2002).28
*30From the language and structure of the statute alone, we find the regulation to be inconsistent with the expressed intent of Congress.29 Still, we do not lightly overturn regulations.
D. Legislative History
Questions have been raised about the appropriateness of use of legislative history at stage one of the Chevron analysis. See, e.g., Coke v. Long Island Care at Home, Ltd., 376 F.3d 118, 127 (2d Cir.2004). In fact, the Supreme Court has often referred to legislative history at stage one, most recently in Gen. Dynamics Land Sys., Inc. v. Cline, 540 U.S. 581, 124 S.Ct. 1236, 1243, 157 L.Ed.2d 1094 (2004), and in a series of earlier cases. See FDA v. Brown & Williamson Tobacco Corp., 529 U.S. 120, 133, 120 S.Ct. 1291, 146 L.Ed.2d 121 (2000) (using “later [congressional] Acts” which spoke “more specifically to the topic at hand” to determine whether the statute evidenced a clear congressional intent in Chevron step one); MCI Telecomms. v. AT & T, 512 U.S. 218, 232-33, 114 S.Ct. 2223, 129 L.Ed.2d 182 (1994) (examining legislative histories of later enactments and finding them inconclusive); Pauley, 501 U.S. at 697-99, 111 S.Ct. 2524 (examining the text of statute and legislative history to determine that Congress intended to delegate to the agency broad policymaking discretion); Pension Benefit Guar. Corp. v. LTV Corp., 496 U.S. 633, 648-50, 110 S.Ct. 2668, 110 L.Ed.2d 579 (1990) (using legislative history in Chevron step one as another “traditional tool[ ] of statutory construction” to conclude that the statute did not “evince a clear congressional intent”); Bowen v. Georgetown Univ. Hosp., 488 U.S. 204, 214, 109 S.Ct. 468, 102 L.Ed.2d 493 (1988) (using legislative history as a check where statutory text is clear that the Secretary had no authority); Japan Whaling Ass’n v. Am. Cetacean Soc’y, 478 U.S. 221, 233-41, 106 S.Ct. 2860, 92 L.Ed.2d 166 (1986) (examining legislative history and determining that Congress has not directly spoken to the issue).30
*31Our view is that where traditional doctrines of statutory interpretation have permitted use of legislative history, its use is permissible and even may be required at stage one of Chevron. This appears to be the functional , approach of some other circuits as well. See Coke, 376 F.3d at 127 (using legislative history at step one “without attaching primacy” to it); Am. Rivers v. F.E.R.C., 201 F.3d 1186, 1196 & n. 16 (9th Cir.2000) (adhering to the practice of considering legislative history in Chevron step one).
Our approach encompasses the traditional rule that where the plain text of the statute is unmistakably clear on its face, there is no need to discuss legislative history. See Sutton v. United Air Lines, Inc., 527 U.S. 471, 481, 119 S.Ct. 2139, 144 L.Ed.2d 450 (1999). Sutton, however, does not go on to say that resort to legislative history is impermissible where used as a check on the understanding of the statute as viewed in light of its text and the statutory scheme as a whole. Even the dissent in General Dynamics admits that legislative history may confirm whether the plain text reading is correct. Gen. Dynamics Land Sys., Inc., 124 S.Ct. at 1252 (Thomas, J., dissenting) (“Although the statute is clear, and hence there is no need to delve into the legislative history, this history merely confirms that the plain reading of the text is correct.”). Indeed, Justice Thomas’s dissent (joined by Justice Kennedy) itself considers legislative history. Id. at 1252-55; see also Pension Benefit Guar. Corp., 496 U.S. at 649, 110 S.Ct. 2668; Bowen, 488 U.S. at 214, 109 S.Ct. 468 (using legislative history as a check where statutory text is clear that the Secretary had no authority); Japan Whaling Ass’n, 478 U.S. at 233-41, 106 S.Ct. 2860 (looking at legislative history to see whether it contradicts implicit grant of authority to agency in statutory text).
This circuit has used the approach of considering legislative history in Chevron stage one analysis where appropriate to discern and/or to confirm legislative intent. See Goldings v. Winn, 383 F.3d 17, 21 (1st Cir.2004) (“If the language of the statute is plain and admits of no more than one meaning or if the statute’s legislative history reveals an unequivocal answer as to the statute’s meaning, we do not look to the interpretation that may be given to the statute by the agency charged with its enforcement”) (emphasis added) (quoting Arnold v. United Parcel Serv., Inc., 136 F.3d 854, 858 (1st Cir.1998)); Arnold, 136 F.3d at 858 (resorting to legislative history when the text of the statute is not unambiguously clear); see also Strickland v. Comm’r, Maine Dept. of Human Servs., 48 F.3d 12, 17, 20 (1st Cir.1995) (examining legislative history, “albeit skeptically,” in Chevron step one).
The perceived dangers of the use of legislative history are particularly lessened where the legislative history is used as a check on an understanding obtained from text and structure. As we shall see, the legislative history, which is not disputed by the respondent, seems to pose none of the problems of potential manipulation of the system by members of Congress. See Strickland, 48 F.3d at 17 n. 3 (reciting the arguments of critics that “legislative history is written by staffers rather than by Congress itself; that it is easily manipulated; that it complicates the tasks of execution and obedience; and that it often is *32shaped by members of Congress who cannot achieve passage of a desired interpretation in the actual text of an enacted statute”).
In light of Supreme Court case law there is no reason to think legislative history may not play other roles then simply confirming a reading obtained by text and structure at stage one.31 Our use of the legislative history in that fashion is, we think, unexceptional.
We look to legislative history to check our understanding and determine whether there is a clearly expressed intention by the Congress which is contrary to the plain language of the statute. See Cardoza-Fonseca, 480 U.S. at 432 & n. 12, 107 S.Ct. 1207. Petitioner argues that the legislative history evidences Congress’s intention to give parolees, regardless of whether they were in removal proceedings, the ability to adjust status and that this intention is consistent with the goals Congress wanted to accomplish in enacting the legislation.
The INA, enacted in 1952, allowed “[t]he status of an alien who was lawfully admitted to the United States as a bona fide nonimmigrant” to be adjusted to that of permanent resident alien if the alien met certain other eligibility requirements. Pub.L. No. 414, 66 Stat. 163, 217 (1952).
The version of 8 U.S.C. § 1255(a) relevant to this case was established in 1960, when Congress amended 8 U.S.C. § 1255 to include paroled aliens as eligible for adjustment of status. Pub.L. No. 86-648, 74 Stat. 504, 505 (1960). At the time the amendment was passed, the statutory provision for the granting of parole to certain inadmissible aliens was substantially similar to the statute governing parole today.32
The legislative history of the 1960 amendments is explicit that Congress recognized numerous problems with the process for adjustment of status under the 1952 law and believed these problems were of serious concern. The Senate Report states:
The Administrative Operations in the application of [the adjustment of status provision], and other related features of the General Immigration Law regarding adjustment of status of aliens within the United States, have been the subject of close scrutiny by the Committees on the Judiciary of both the Senate and the House of Representatives. For a considerable period of time, there has appeared to be a steadily mounting number of cases in which aliens determined by the Immigration and Naturalization Service to be eligible for permanent res*33idence in the United States in accordance with all the applicable provisions of the Immigration and Nationality Act, had to comply with what appeared in those cases to be an unnecessary procedure known as preexamination and voluntary departure with a view toward applying for an immigrant visa in one of the U.S. Consular Offices in Canada. During the Fiscal Year ending June 30, 1958, more than 7,000 aliens in the United States had their eligibility to enter as immigrants determinated in this country prior to sending them to Canada where they briefly appeared before a U.S. consular officer, and then returned to this country with an immigrant visa.
In addition, the review of a considerable number of private relief immigration bills seeking adjustment of status of nonimmigrants has further demonstrated to the Committee the desirability of general amendatory legislation on this subject.
S.Rep. No. 86-1651 (1960), reprinted in 1960 U.S.C.C.A.N. 3124, 3136.
The Report states that Congress, in amending the adjustment of status statute, wished to avoid a situation that,
not only necessitate^] the reinstatement of the fallacious procedure known as ‘preexamination’ and consisting of round trips to Canada for the' sole purpose of obtaining an immigrant visa, but will certainly greatly increase the number of private bills. The Congress has repeatedly expressed its disapproval of the ‘preexamination’ procedure and has similarly expressed its dissatisfaction with the mounting volume of private legislation.
Id. at 3137.
In response to those problems, Congress in 1960 amended the adjustment of status provision. The new provision read: “The status of an alien, other than an alien crewman, who was inspected and admitted or paroled into the United States may. be adjusted ... to that of an alien lawfully admitted for permanent residence....” 74 Stat. at 505. This change- broadened the category of individuals eligible for adjustment of status relief. S.Rep. No. 86-1651 (1960), reprinted in 1960 U.S.C.C.A.N. 3124, 3125.33
In changing the system, Congress sought to ameliorate three types of problems caused by .the old system.. Congress wished to eliminate the burden on inspected and admitted or paroled aliens and their American relatives of having to leave the United States and apply from a eonsu-*34lar office abroad (often from Canada).34 See id. at 3137 (“Aliens eligible to benefit from this legislation ... would also save the expense of journeys to Canada, rather high when consideration is given to the fact that many of the prospective eligible immigrants live with their families in areas rather remote from the U.S. Consular offices in Canada.”).
Congress was also concerned with the costs to the government of the then extant system, caused by the large number of private bills presented to it for adjustment of status for named individuals. Congress had repeatedly expressed its “dissatisfaction with the mounting volume of private legislation” introduced to adjust the status of certain aliens. Id. at 3137. By adopting the 1960 legislation, Congress wished to alleviate this burden on itself. See id. at 3136. There is some evidence in the legislative history that Congress wished also to alleviate the burden imposed on consular offices to process applications for adjustment of status. The Senate Report emphasizes that in fiscal year 1958, alone, over 7,000 individuals had to leave the United States and apply for a visa in Canada. Id. Indeed, the Department of State commented on the legislation.
Finally, in expanding the group of individuals eligible for adjustment of status, Congress clearly evaluated the administrative inconvenience to the INS of the expanded category of those eligible to apply for adjustment of status and nonetheless altered the prior procedure. Indeed, the administrative burdens of the various provisions involved were given “close scrutiny” by Congress. Id.
The effect of the regulation before us, limiting the ability of paroled aliens in removal proceedings to adjust status, will predictably be to re-institute the very problems which Congress attempted to eliminate in 1960. It forces paroled aliens in removal proceedings to leave the country to apply for adjustment of status. This imposes considerable burdens on the aliens and, where applicable, their American spouses and relatives. The effect of the regulation, predictably, will be to increase the number of private bills seeking individual adjustment of status, thus burdening Congress. It will also increase the burden on consular offices abroad, because aliens who are otherwise available to adjust status will now have to apply through the consular office.
The 1960 legislative history of 8 U.S.C. § 1255(a) confirms and enhances our understanding of the statute.
E. Effect of IIRIRA
We consider briefly the arguments of both sides that rely on later revisions to the INA, specifically IIRIRA, to support their different understandings of what Congress meant in the adjustment of status provisions of 8 U.S.C. § 1255. There is no claim that section 1255(a) was amended by IIRIRA or any other statute in any relevant way.
The Attorney General relies on provisions of IIRIRA to argue that the original understanding of the statute in 1960 must *35be altered in light of 'later law, and the statute must now be read as introducing at least ambiguity into section 1255(a), despite the fact that section 1255(a) itself was not amended. The Attorney General argues that new regulations were required due to IIRIRA’s replacement of “entry” with “admission” as the criterion which determines which of two sets of grounds of removal, 8 U.S.C. § 1882(a) or 8 U.S.C. § 1227, applies in removal proceedings. Further, the Attorney General argues, under 8 U.S.C. § 1182(d)(5)(A), a parole of an alien is not the admission of that alien.
Our earlier analysis of the meaning of 8 U.S.C. § 1255(a) in light of the statutory context takes into account the statutory scheme as it exists under IIRIRA. The Attorney General’s arguments do not change this, understanding; they are unpersuasive because they do not concern the eligibility of paroled aliens to apply for adjustment of status under section 1255(a) or in any way act to limit the eligibility of paroled individuals — a group Congress specifically deemed eligible — to adjust status. The classification of paroled aliens as “not admitted” is not new to the passage of IIRIRA and does not change the treatment of parolees. Also, the reclassification of aliens “present pursuant to an entry” to “applicants for admission” does not affect the status of paroled aliens, who have always been considered applicants for admission.
The petitioner relies on IIRIRA for two points. Specifically, the petitioner argues that since 1960 the agency and Congress have consistently understood the statute to be as petitioner reads it. Moreover, in the major revisions .of the immigration laws since 1960, which largely restricted aliens’ efforts to remain in this country, Congress has never once restricted the ability of paroled aliens to apply for adjustment of status.
.This confirms our understanding of the clear meaning of the statute.35 Consistent with our interpretation of the statute, in our view, the changes to the statute with the passage of IIRIRA work against the Attorney General’s argument, not in favor of it. Under IIRIRA and previous amendments, Congress amended section 1255 to limit the eligibility for adjustment' of status so that certain types of aliens may not apply. Historical & Statutory Notes, 1996 Amendments, 8 U.S.C.A. § 1255. Congress has directly addressed the issue of eligibility for adjustment of status on several occasions, yet these amendments did not limit the category of paroled aliens who may apply for adjustment of status, and they neither gave the Attorney General discretion to redefine eligibility nor did they endorse the additional restrictions on eligibility contained in the Attorney General’s regulation. See Brown & Williamson Tobacco, Corp., 529 U.S. at 137, 120 S.Ct. 1291 (relying in part on later actions of Congress which specifically address the regulation of tobacco as evidence that the FDA did not have authority to regulate tobacco).
F. Reasonableness
Many of the Attorney General’s arguments go to the reasonableness of the regulation. This is a Chevron step two argument. But as previously explained, *36this is a Chevron step one case, and even the Attorney General’s reasonable actions cannot control in the face of clear contrary congressional intent.
Even where there is ambiguity, reasonableness is assessed in light of the statutory scheme. For example, the Attorney General justifies the regulation on the basis that the exercise of discretion was consistent with Congress’s desire to speed up the removal process through expedited removal proceedings. 62 Fed.Reg. 444, 452 (Jan. 3, 1997). The desire for administrative efficiency cannot displace clear congressional intent.
Also, the Attorney General argues he has a facially legitimate and bona fide reason for the regulation, citing to the Immigration Control and Financial Responsibility Act of 1996,36 which was intended to “increase control over immigration ... expediting the removal of excludable and deportable aliens, especially criminal aliens, and reducing the abuse of parole and asylum provisions.”37 S.Rep. No. 104-249 at 2 (1994) (not reported in U.S.C.C.A.N.). The short reply is that Congress did not, even in 1996, give the Attorney General unfettered discretion to expedite removal and reduce abuse of parole in disregard of the statutory scheme. Congress expressly did not alter the basic structure of eligibility for application for adjustment of status while simultaneously making a limited category of parolees ineligible. See Cardoza-Fonseca, 480 U.S. at 444-45, 107 S.Ct. 1207 (noting the agency cannot ignore Congress’s desired scheme in the asylum area).
Finally, the position that the Attorney General takes in the 1997 regulation is inconsistent with the agency’s long-standing previous practice. Arriving aliens in removal proceedings were always able to adjust status before the district director prior to the promulgation of the 1997 regulations. See In re Castro-Padron, 21 I. & N. Dec. 379, 1996 WL 379828 (BIA 1996). As noted in Cardozar-Fonseca, “An additional reason for rejecting the [Attorney General’s] request for heightened deference to [his] position is the inconsistency of the positions the [agency] has taken through the years. An agency interpretation of a relevant provision which conflicts with the agency’s earlier interpretation is ‘entitled to considerably less deference’ than a consistently held agency view.” Cardoza-Fonseca, 480 U.S. at 446 n. 30, 107 S.Ct. 1207 (quoting Watt v. Alaska, 451 U.S. 259, 273, 101 S.Ct. 1673, 68 L.Ed.2d 80 (1981)). So even if there were ambiguity in section 1255(a), the agency would be entitled to less than normal deference.
V.
We find the regulation, 8 C.F.R. § 245.1(c)(8), to be invalid as inconsistent with 8 U.S.C. § 1255(a); accordingly we vacate the removal order and remand the case to the BIA for proceedings consistent with this opinion. So ordered.