Reversed by published opinion. Judge LUTTIG wrote the opinion, in which Judge MICHAEL joined. Senior Judge BALDOCK wrote a dissenting opinion.
[386]*386OPINION
LUTTIG, Circuit Judge.
Petitioner Olatunji appeals from the district court’s denial of his 28 U.S.C. § 2241 habeas petition, which sought review of his continued detention by the INS pursuant to a final order of removal issued by the Board of Immigration Appeals. For the reasons that follow, the judgment of the district court is reversed and the habeas petition is granted.
I.
Clifford K. Olatunji, a citizen of Nigeria, has been in the United States on an ongoing basis since 1984. He became a lawful permanent resident in 1993. J.A. 116. In 1994, Olatunji was arrested for illegally selling insurance policies and stealing government property. He subsequently pled guilty to one count of theft of government property in violation of 18 U.S.C. § 641, J.A. 133-35, and was sentenced to two months of confinement in a community treatment center, fined $259, ordered to pay $2,296 in restitution, and placed on probation for two years. Id.
In 1998, Olatunji traveled to London for nine days. Upon his return, he sought to re-enter the United States as a lawful permanent resident. J.A. 198-99. He disclosed his 1994 conviction and, pursuant to provisions of the Illegal Immigration Reform and Immigrant Responsibility Act (“IIRIRA”) enacted after 1996, was accordingly classified as a lawful permanent resident seeking “admission” into the United States, 8 U.S.C. § 1101(a)(13)(C)(v). He was subsequently deemed inadmissible because of that conviction. J.A. 153-53; 8 U.S.C. § 1182(a)(2)(A). After a hearing before an Immigration Judge, Olatunji was ordered to be removed from the United States to Nigeria. J.A. 183-84. His appeal to the Board of Immigration Appeals was unsuccessful. Id. at 187-89.
Instead of directly appealing the Board’s decision to this court, Olatunji filed a pro se petition for a writ of habeas corpus in the district court. He argued, inter alia, that IIRIRA’s criminal inadmissibility provisions were impermissibly retroactive to his decision to plead guilty and that his removal under IIRIRA would violate the Fifth Amendment’s Due Process Clause. The district court exercised jurisdiction over Olatunji’s claims and denied the petition on the merits. J.A. 196-205.
II.
As to the threshold question of the district court’s jurisdiction, title 8, section 1252(a)(2)(C), of the United States Code, 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 [crime involving moral turpitude].” Despite this plain language, the government urges that direct review of Olatunji’s “substantial constitutional claims” is permitted under IIRIRA and that Olatunji’s instant habeas petition is precluded by his failure to seek relief on direct review.
As the government notes, at least two of our sister circuits have agreed with its interpretation of IIRIRA. Respondent’s Br. at 14. Both of these authorities, Roble-do-Gonzales v. Ashcroft, 342 F.3d 667 (7th Cir.2003)1 and Patel v. INS, 334 F.3d [387]*3871259, 1262-63 (11th Cir.2003), rest on the following dicta, and in particular the government’s concession that is referenced within this dicta, which appears in Justice Stevens’ opinion for the Court in Calcano-Martinez v. INS, 533 U.S. 348, 121 S.Ct. 2268, 150 L.Ed.2d 392 (2001):
The scope of [§ 1252(a)(2)(C) ] is not entirely clear. Though the text of the provision is quite broad, it is not without its ambiguities.... [T]he government has ... coneeded that the courts of appeals retain jtmsdiction to review “substantial constitutional challenges” raised by aliens ivho come within the strictures of § 1252(a)(2)(C). As the petitions in this case do not raise any of these types of issues, we need not address this point further. Nonetheless, it remains instructive that the government acknowledges that background principles of statutory construction and constitutional concerns must be considered in determining the scope of IIRIRA’s jurisdiction-stripping provisions.
Id. at 350 n. 2, 121 S.Ct. 2268 (emphasis added).
This dicta, and its referenced concession, must be understood in the context of the government’s full proposal as to the proper interpretation of section ,1252(a)(2)(C) in Calcano-Martinez. There, the government maintained that by enacting IIRI-RA’s jurisdiction-stripping provisions, “Congress ha[d] also precluded the district courts from reviewing challenges ... by habeas corpus or otherwise,” and that “Congress’s unmistakable intent in the judicial review provisions of [IIRIRA] [was] to channel all challenges ... into the courts of appeals.” Brief for the Respondent at 14, 533 U.S. 348, 121 S.Ct. 2268, 150 L.Ed.2d 392 (2001) (emphasis added). It was as a consequence of this understanding that the government interpreted section 1252(a)(2)(C) to permit direct1 review in the Courts of Appeals, in order , to avoid the “serious constitutional question that would arise if a federal statute were construed to deny any judicial forum for a colorable constitutional claim.” Webster v. Doe, 486 U.S. 592, 603, 108 S.Ct. 2047, 100 L.Ed.2d 632 (1988) (emphasis added).
But as the Supreme Court made clear in St. Cyr, IIRIRA’s jurisdiction-stripping provisions in fact do not eliminate the district courts’ habeas jurisdiction under 28 U.S.C. § 2241. INS v. St. Cyr, 533 U.S. 289, 313-14, 121 S.Ct. 2271, 150 L.Ed.2d 347 (2001). Thus, the entire premise for the government’s assertion in Calcano-Martinez, that direct review of substantial constitutional claims must exist because no other avenue of review1 — -including habeas corpus — was available, was no longer of any moment after St. Cyr. And indeed, the authorities cited by the government in Cal-cano-Martinez in support of its proposed interpretation simply noted the serious constitutional question that would arise if Congress eliminated all judicial review of constitutional challenges to removal and deportation decisions, decisions that have no relevance where a forum to litigate substantial constitutional claims does exist. See Cedano-Viera v. Ashcroft, 324 F.3d 1062, 1069 (9th Cir.2003) (“[T]he thrust of the opinion in Calcano-Martinez, together with the Court’s opinion in St. Cyr ... is that jurisdiction over constitutional issues [388]*388... is withdrawn from the courts of appeals and that the place to resolve such issues is the district courts through habeas corpus.”).
Consistent with our interpretation of section 1252(a)(2)(C), as informed by St. Cyr, where Congress has provided a forum for litigating constitutional claims, the Supreme Court has declined to read exceptions into unambiguous statutes limiting federal jurisdiction. See Weinberger v. Salfi, 422 U.S. 749, 762, 95 S.Ct. 2457, 45 L.Ed.2d 522 (1975) (refusing to read a constitutional challenge exception into 42 U.S.C. § 405(h) of the Social Security Act, barring jurisdiction under § 1331 “to recover on any claim arising under [Title II of the Social Security Act],” because the Social Security Act “itself provides jurisdiction for constitutional challenges to its provisions”); see also Cedano-Viera, 324 F.3d at 1070 (“[T]he Webster rule turned on the absence of any other available forum, which is not the case with respect to ... § 1252(a)(2)(C), because all routes to the courthouse are not closed when there is an opportunity for habeas relief.”); Flores-Miramontes v. INS, 212 F.3d 1133, 1136 (9th Cir.2000).
In sum, the mandate of section 1252(a)(2)(C) that “no court shall have jurisdiction to review any final order of removal” plainly extends to all claims on direct review, including constitutional claims. That St. Cyr’s holding rested on the purported legal and historical distinction between “jurisdiction to review” and “habeas corpus,” see 533 U.S. at 311-312, 121 S.Ct. 2271, confirms that such is the correct interpretation of section 1252(a)(2)(C)’s unambiguous prohibition. Section 1252(a)(2)(C) should, accordingly, be enforced without exception. The contrary interpretation would allow petitioners multiple opportunities to pursue their constitutional claims in the face of a jurisdiction-stripping statute that is unquestionably enacted to curtail such access to judicial review. Olatunji being barred from pursuing direct review in the courts of appeals under IIRIRA, the district court properly exercised its jurisdiction pursuant to section 2241.
III.
Turning to the merits of the dispute before us, Olatunji contends that IIRIRA has attached new legal consequences to his 1994 decision to plead guilty and that this is impermissible under the well established presumption against retroactive application of statutes. The government and the dissent agree with the first half of this contention, namely that Olatunji would have been free, prior to IIRIRA’s enactment, to travel abroad after his guilty plea and that the sole reason under IIRIRA that Olatunji can no longer travel abroad without facing removal proceedings is his decision to plead guilty. Respondent’s Br. at 21-24; post at 29. The government and dissent nonetheless maintain, despite the longstanding presumption against retroac-tivity, that IIRIRA’s retroactive application is permissible unless Olatunji can demonstrate that he “almost certainly relied” upon his ability to take brief trips abroad when he entered his plea. Post at 29 citing St. Cyr, 533 U.S. at 325, 121 S.Ct. 2271. And the government further suggests that it can defeat the presumption against retroactivity merely by notifying aggrieved parties of the adverse consequences of the statutes it seeks to enforce retroactively.
Believing that these twin requirements would all but turn the presumption against retroactivity on its head, we hold that reliance (whether subjective or objective) is not a requirement of impermissible retro-activity and that the government’s notice is insufficient to overcome the impermissibly [389]*389retroactive effect of IIRIRA on Olatunji’s guilty plea.2
A.
Where, as here, Congress has not clearly spoken as to a statute’s temporal application, we begin with a “presumption against retroactive legislation” that is “deeply rooted in our nation’s jurisprudence,” Landgraf v. USI Film Products, 511 U.S. 244, 265, 114 S.Ct. 1483 (1994).3 A statute will be held to have an impermissible retroactive effect when it “takes away or impairs vested rights acquired under existing laws, or creates a new obligation, imposes a new duty, or attaches a new disability, in respect to transactions or consideration already past.” St. Cyr, 533 U.S. at 321, 121 S.Ct. 2271 (quoting Society for Propagation of the Gospel v. Wheeler 22 F. Cas. 756, 767, No. 13, 1356 (C.C.D.N.H. 1814) (Story, J.)). “[T]he'judgment whether a particular statute acts retroactively should be informed and guided by familiar considerations of fair notice, reasonable reliance, and settled expectations.” Landgraf, 511 U.S. at 270, 114 S.Ct. 1483.
Whether, under the Landgraf framework, an aggrieved party must demonstrate some form of reliance on a prior statute in order to establish that a later-enacted statute is impermissibly retroactive has not been resolved by the Supreme Court. The government and the dissent claim, purportedly under Landgraf, that Olatunji must establish that he “almost certainly relied upon” pre-IIRIRA law to his detriment, Respondent’s Br. at 30-31; post at 43-44 citing St. Cyr, 533 U.S. at 325, 121 S.Ct. 2271, and that he did not so rely. The proposed imposition of a subjective reliance requirement is understandable in light of the Supreme Court’s confusing treatment of the subject, beginning in Landgraf and continuing through St. Cyr. However, we do not believe that subjective reliance is, or ought to be, relevant to the question of whether a particular statute is impermissibly retroactive, as such is neither dictated by Supreme Court precedent nor related to the presumption of congressional intent underlying the bar against retroactivity.
A careful review of both the basis for the judicially-imposed presumption against retroactivity and the Supreme Court’s ret-roactivity jurisprudence shows that the fact that IIRIRA has attached new legal consequences to Olatunji’s guilty plea is, alone, sufficient to sustain his claim, and that no form of reliance is necessary. If some form of reliance were understood as required by the Supreme Court’s teachings on the subject, it could only be objectively reasonable reliance. It is impossible to infer from those teachings the requirement of subjective reliance proposed by the government and the dissent.
1.
Retroactivity is a question of congressional intent. In the face of congressional silence on the temporal reach of a given statute, it is presumed that Congress did not intend for the statute to be applied retroactively. See Landgraf, 511 U.S. at 271, 114 S.Ct. 1483 (“Since the early days of this Court, we have declined, to give retroactive effect to statutes burdening private rights unless Congress , had made [390]*390clear its intent.”); id. at 286, 114 S.Ct. 1483 (“A legislator who supported a prospective statute might reasonably oppose retroactive application of the same statute. Indeed, there is reason to believe that the omission of ... express retroactivity provisions was a factor in the passage of the ... bill.”). Neither the dissent nor the government even attempts to relate its subjective reliance requirement to this fundamental underpinning of the prohibition on statutory retroactivity.
Consistent with the understanding that retroactivity is a question of congressional intent, courts have historically asked simply whether the statute in question attached “new legal consequences to events completed before its enactment.” Id. at 268, 114 S.Ct. 1483. Thus, as Justice Story wrote in his oft-quoted formulation, “every statute, which takes away or impairs vested rights acquired under existing laws, or creates a new obligation, imposes a new duty, or attaches a new disability, in respect to transactions or considerations already past, must be deemed retrospective.” Society for Propagation of the Gospel, 22 F. Cas. at 767. Indeed, the Land-graf Court itself relied upon numerous cases where the retroactivity determination appears to have been based exclusively on the factual question of whether the statute “change[d] the legal consequences of acts completed before its effective date.” Id. at 268 n. 23, 114 S.Ct. 1483.
Recent Supreme Court decisions, beginning with Landgraf itself, admittedly can be read as suggesting that Justice Story’s formulation is not necessarily the whole of the retroactivity inquiry. In Landgraf, for example, the Court noted the influence of Justice Story’s formulation, but then observed as follows:
The conclusion that a particular rule operates “retroactively” comes at the end of a process of judgment concerning the nature and extent of the change in the law and the degree of connection between the operation of the new rule and a relevant past event. Any test of retroactivity will leave room for disagreement in hard cases, and is unlikely to classify the enormous variety of legal changes with perfect philosophical clarity. However, retroactivity is a matter on which judges tend to have ‘sound instincts,’ ... and familiar considerations of fair notice, reasonable reliance, and settled expectations offer sound guidance.
Id. at 270, 114 S.Ct. 1483 (citations omitted) (emphasis added).
Landgraf’s ambiguous treatment of reliance has generated substantial confusion as to whether a party must prove some form of reliance in order to demonstrate that a statute is impermissibly retroactive. This confusion exists within the Supreme Court, in its decisions postdating Land-graf. Compare, e.g., Hughes Aircraft Co. v. United States ex rel. Schumer, 520 U.S. 939, 946, 117 S.Ct. 1871, 138 L.Ed.2d 135 (1997)(holding that the elimination of certain defenses to qui tarn suits under the False Claims Act was impermissibly retroactive without discussing whether Hughes Aircraft detrimentally relied on the prior statutory scheme), with St. Cyr, 533 U.S. 289, 121 S.Ct. 2271, 150 L.Ed.2d 347 (observing that aliens who had entered plea agreements prior to IIRIRA’s enactment had relied on the possibility of receiving section 212(c) waivers and holding that IIRIRA could not be retroactively applied to such aliens). The confusion extends throughout the Courts of Appeals. Compare Ponnapula v. Ashcroft, 373 F.3d 480 (3rd Cir.2004) (holding that, irrespective of subjective reliance, IIRIRA cannot be retroactively applied as a bar to section 212(c) discretionary waivers to aliens who declined plea agreements and elected to go [391]*391to trial), with Rankine v. Reno, 319 F.3d 93, 99 (2d Cir.2003) (holding that IIRIRA could be retroactively applied as a bar to section 212(c) discretionary waivers to aliens who elected to go to trial because “none of these petitioners detrimentally changed his position in reliance on continued eligibility for § 212(c) relief’ and because in St. Cyr “it was reliance, and the consequent change in immigration status, that produced the impermissible retroactive effect of IIRIRA”). And, unsurprisingly, the same confusion exists among the parties to suit in the federal courts. In this very case, the government vacillated in response to the pointed question of whether reliance remains a requirement after Hughes Aircraft.
Although Landgraf’s, ambiguity has engendered a significant amount of confusion, neither Landgraf’s holding nor subsequent Supreme Court authority supports a subjective reliance requirement. Certainly Justice Story’s familiar statement of the test for determining statutory retroac-tivity — which the Court held in Hughes Aircraft was sufficient to demonstrate ret-roactivity — makes no mention of reliance. See Hughes Aircraft, 520 U.S. at 947, 117 S.Ct. 1871. And neither is there any reason instinctively to believe that subjective reliance properly should be a consideration in retroactivity analysis: Whether a plaintiff did or did not rely on a prior statutory scheme is irrelevant to whether that scheme in fact has a retroactive effect on that plaintiff. “It is,” as the Third Circuit has noted, “a strange ‘presumption’ ... that arises only on so heightened a showing as actual reliance.” Ponnapula, 373 F.3d at 491.
In Landgraf, the Court confronted the question of whether the Civil Rights Act of 1991, which created a right to recover compensatory and punitive damages for certain violations of Title VII of the Civil Rights Act of 1964, could be applied to conduct occurring before the 1991 Act. The court acknowledged that “concerns of unfair surprise and upsetting expectations are attenuated in the case of intentional employment discrimination, which has been unlawful for more than a generation,” but nonetheless held the statute impermis-sibly retroactive because “[e]ven where the conduct in question is morally reprehensible or illegal, a degree of unfairness is inherent whenever the law imposes additional burdens on conduct that occurred in the past.” Id. at 283 n. 35, 114 S.Ct. 1483 (emphasis added).
That the Supreme Court in Landgraf did not intend to impose a requirement of reliance is confirmed by Hughes Aircraft. There, the Court held that the elimination of certain defenses to qui tam suits under the False Claims Act could not be applied retroactively to Hughes Aircraft. And it so held without even a single word of discussion as to whether Hughes Aircraft — or, for that matter, similarly situated government contractors — had relied on the eliminated defense to its detriment. Contrary to the dissent’s contention, if reliance were indeed a requirement, the Court almost certainly would have addressed the question or at least remanded for a factual determination of whether Hughes Aircraft had or had not relied upon the prior statutory scheme. It is exceedingly unlikely that the Court simply overlooked the factor.
And if this were not enough, our own Circuit has so interpreted Hughes Aircraft. In Velasquez-Gabriel v. Crocetti, 263 F.3d 102, 109 (4th Cir.2001), not only did we emphasize that Hughes Aircraft “h[eld] that the amended False Claims Act operated retroactively without discussing whether any party detrimentally relied on previous law,” but we ourselves stated that the fact “[tjhat Velasquez-Gabriel did not [392]*392detrimentally rely on prior law may not, however, foreclose a claim that § 241(a)(5) nonetheless operates retroactively.” See also Chambers v. Reno, 307 F.3d 284, 292-93 (4th Cir.2002) (“In view of these observations by the Court [in Hughes Aircraft ] about retroactivity, we have acknowledged that an alien’s failure to demonstrate reliance on pre-IIRIRA law might not foreclose a claim that the post-IIRIRA version of the INA operates retroactively.”). Inexplicably, the dissent does not even attempt to address our Circuit’s interpretation of Hughes Aircraft in the context of IIRIRA retroactivity claims.
The dissent maintains that our Circuit has held in Velasquez-Gabriel, Chambers, and Tasios v. Reno, 204 F.3d 544 (4th Cir.2000) that reliance is required in order to find a statute impermissibly retroactive. Post at 25-27. But it has not. The dissent simply misreads these authorities. In none of these cases did we hold that an alien must show detrimental reliance upon pre-IIRIRA law to establish a retroactivity claim. While in Velasquez-Gabriel and Chambers, we concluded that neither petitioner had relied upon pre-IIRIRA law, in both cases we specifically declined — in light of Hughes Aircraft — to rest our holding on this conclusion. In fact, as the preceding quotations from these cases make clear, far from holding that reliance is the sine qua non of retroactivity, both Chambers and Velasquez-Gabriel said precisely the opposite, that even aliens who have not detrimentally relied on pre-IIRI-RA law can sustain a claim that IIRIRA is impermissibly retroactive.
Velasquez-Gabriel, who was “represented by counsel the entire time,” was denied relief because he could have completely avoided the retroactive effect of IIRIRA by applying to adjust his status under pre-IIRIRA law, including during the six months between IIRIRA’s passage and its effective date. Velasquez-Gabriel, 263 F.3d at 109-10. Chambers was denied relief because IIRIRA did not attach new consequences to his “relevant past conduct,” namely his decision to go to trial, and was therefore not retroactive in fact Chambers, 307 F.3d at 293. Thus, Chambers did not even fall under the Justice Story retroactivity framework because his “decision to go to trial did not render him deportable or subject him to certain deportation, regardless of whether pre- or post-IIRIRA law applied.” Id. (emphasis in original). Indeed, that IIRIRA was not substantively retroactive to Chambers’ relevant past conduct was the exclusive distinction offered by the Chambers court to Velasquez-Gabriel’s reservation that under Hughes an alien is not foreclosed from a retroactivity challenge to IIRIRA by his inability to demonstrate subjective reliance. Id.
Suffice it to say that neither Velasquez-Gabriel’s ability to avoid the costs of IIRI-RA’s enactment nor Chambers’ inability to demonstrate that IIRIRA was substantively retroactive under Justice Story’s framework bears in any way on Olatunji’s claim. As demonstrated below, Olatunji could not avoid the cost of IIRIRA because that legislation either entirely foreclosed his ability to travel abroad — a cost not attendant to his plea agreement — or it subjected him to deportation upon reentry. For the same reason, IIRIRA’s effect on Olatunji is indisputably retroactive substantively, i.e. retroactive in fact, under Justice Story’s formulation.
Tasios holds nothing different from Chambers or Velasquez-Gabriel. In Tas-ios, we held that AEDPA section 440(d) had “an undeniably retroactive effect” on pre-enactment guilty pleas and therefore could not pose a bar to discretionary relief under section 212(c). Tasios, 204 F.3d at 550. Confronting the “dictum” from De [393]*393Osorio v. INS, 10 F.3d 1034, 1041-42 (4th Cir.1993) that “the De Osorios could not plausibly argue that they relied on the availability of discretionary relief when they chose to violate the drug laws,” Tas-tos, 204 F.3d at 550, we explained that “we do not limit our analysis to the conduct that resulted in the felony conviction.” Instead, we held, guilty pleas and concessions of deportability are also “conduct” the “legal effect” of which can be imper-missibly “determined by subsequently enacted law.” Id. at 551. We did observe that the relevant difference between these categories of previously completed conduct (ie., felonious offense and a lawful plea agreement or concession) was the possibility of “reasonable! ] reliance! ].” But we granted relief without holding — or even discussing for that matter — that Tasios was required to demonstrate that he subjectively relied on section 212(c) when he entered his plea.
And not only is our holding today consistent with our circuit precedent, it is also consistent with Supreme Court precedent, notwithstanding the dissent’s contention otherwise. The dissent claims that our holding conflicts with both St. Cyr and Republic of Austria v. Altmann, — U.S. -, 124 S.Ct. 2240, 159 L.Ed.2d 1 (2004). It conflicts with neither.
St. Cyr did not alter the requirements for establishing retroactivity. St. Cyr discussed the fact that “aliens like [St. Cyr], almost certainly relied upon that likelihood [of receiving discretionary relief under § 212(c) ] in deciding whether to forgo their right to a trial.” St. Cyr, 533 U.S. at 325, 121 S.Ct. 2271. But St. Cyr did not purport to add a subjective reliance requirement; rather, it applied Landgraf to a set of facts that indicated “an obvious and severe retroactive effect.” Id. (emphasis added). The “Court regarded St. Cyr as a clear and straightforward result flowing from Landgraf.... St. Cyr was an easy case on the retroactivity issue.” Pon-napula, 373 F.3d at 492-93 (quotation omitted).
Altmann likewise did not establish a reliance requirement. While it is indeed noted in Altmann, as the dissent points out, that the “aim of the presumption [against retroactivity] is to avoid unnecessary post hoc changes to legal rules on which parties relied in shaping their primary conduct,” Altmann, 124 S.Ct. at 2252 (emphasis added), the Court neither said nor held that the legal framework for determining whether a statute is impermissi-bly retroactive includes consideration of reliance. Rather, quoting Landgraf, Alt-mann describes “the presumption against retroactive application” as follows:
When, however, the statute contains no such express command the court must determine whether the new statute would have retroactive effect, ie., whether it would impair rights a party possessed when he acted, increase a party’s liability for past conduct, or impose new duties with respect to transactions already completed. If the statute would operate retroactively, our traditional presumption teaches that it does not govern absent clear congressional intent favoring such a result.
Id. at 2250-51 quoting Landgraf, 511 U.S. at 280, 114 S.Ct. 1483. Not only is reliance conspicuously absent from the “Land-graf default rule,” as the Altmann Court described the governing test, see 124 S.Ct. at 2251, but Altmann’s formulation stands as yet further confirmation that the Supreme Court intends Justice Story’s framework to be sufficient for application of the “traditional presumption,” id., against retroactivity. While in Altmann the Court reaffirms that the presumption against retroactivity serves reliance inter[394]*394ests, it also confirms that reliance is not a requirement of retroactivity.
In sum, the historical presumption against retroactive application of statutes did not require reliance. Neither Land-graf nor subsequent Supreme Court authority imposes any such requirement. And we believe that the consideration of reliance is irrelevant to statutory retroac-tivity analysis.
Justice Story’s formulation, which the Supreme Court has consistently relied upon, asks only whether a statute in fact has retroactive effect, and we would ask no more. If the presumption is that Congress does not intend statutes to operate retroactively (and that is the presumption we indulge), then it follows that if a statute does in fact impose new legal consequences on past actions, Congress did not intend such. Whether the particular petitioner did or did not subjectively rely upon the prior statute or scheme has nothing whatever to do with Congress’ intent — the very basis for the presumption against statutory retroactivity. It is one thing to indulge in the supportable presumption that Congress intends its enactments not to operate retroactively; it is another altogether to indulge the quite different, and unsupported and unsupportable, presumption that Congress so intends, but only where the particular petitioning party can prove that he subjectively relied on the prior statute to his detriment. In other words, where Congress has apparently given no thought to the question of retro-activity whatever, there is no basis for inferring that Congress’ intent was any more nuanced than that statutes should not be held to apply retroactively. Anything more, in the face of complete congressional silence, is nothing but judicial legislation.
Though Judge Baldock believes otherwise, we understand his dissent actually to validate just this. Not only does the dissent admit (internally inconsistent with its own opinion) that the court has never insisted upon reliance as a requirement in retroactivity analysis, but also, by way of omissions, the dissent has betrayed its own understanding that a statute does operate retroactively if, alone, it attaches new legal consequences to prior conduct.
The dissent prominently quotes the Supreme Court’s observation that “the Court has used various formulations to describe the functional conception of legislative ret-roactivity, and made no suggestion that Justice Story’s formulation was the exclusive definition of presumptively impermissible retroactive legislation,” see post at 24 quoting Hughes, 520 U.S. at 947, 117 S.Ct. 1871 (emphasis added). Unrecognized by the dissent, this quoted observation actually establishes the majority’s point and refutes that of the dissent — namely that the Supreme Court has variously articulated the requirements to show retroactivity, has never insisted upon a reliance requirement, and has consistently concluded that Justice Story’s formulation is “sufficient ... for invoking the presumption against retroactivity.” Hughes, 520 U.S. at 947, 117 S.Ct. 1871.
Moreover, in further quotation of the Supreme Court, the dissent states that “a statute does not operate ‘retrospectively’ merely because it is applied in a case arising from conduct antedating the statute’s enactment, or upsets expectations based in prior law,” post at 28 quoting Landgraf 511 U.S. at 269; rather, the dissent confidently asserts, it is “reliance” that the Supreme Court requires in addition to mere application to prior conduct, in order for a law to be impermissibly retroactive. But once again, not only does the passage from which the dissent quotes not bear the interpretation imposed upon the passage by the dissent; it affirmatively [395]*395proves the point upon which the majority rests. For the dissent omits the very next sentence following the sentence it quotes from Landgmf. It is in this omitted sentence that the Court explains what must be asked in addition to whether a statute applies to conduct antedating its enactment. And, tellingly, there, the Court does not identify “reliance” as the further inquiry, as the dissent would have one believe. “[R]other,” said the Supreme Court, “the court must ask whether the new provision attaches new legal consequences to events completed before its enactment,” id. — precisely the standard that we (the majority) adopt today.4
In sum, the dissent asserts concern that we have “ignored Supreme Court precedent,” claiming the Court’s precedent has established a “central role” for reliance in “the ... retroactivity analysis.” Post at 23. But it is hard to take this assertion of concern seriously. For, not only is it beyond dispute that the Supreme Court has not insisted upon reliance in order to hold a law impermissibly retroactive, as we establish above and as the dissent itself acknowledges (albeit unwittingly); but it is the dissent that refuses even to address the Supreme Court precedent that it contends we “ignore,” which precedent, as we demonstrate, does not hold that reliance is required and, indeed, holds laws impermis-sibly retroactive without even so much as a mention of the “reliance” that the dissent steadfastly maintains is essential to the retroactivity analysis.
2.
Olatunji is entitled to relief under the framework that we conclude governs the retroactivity determination. After his 1994 guilty plea but prior to IIRIRA’s enactment, Olatunji would have been free to take brief trips abroad — such as his trip to London — without subjecting himself to removal proceedings. The previously applicable statute governing lawful permanent resident reentry into the United States, former 8 U.S.C. § 1101(a)(13), provided:
The term “entry” means any coming of an alien into the United States, from a foreign port or place or from an outlying possession, whether voluntarily or otherwise, except that an alien having a lawful permanent residence in the United States shall not be regarded as making an entry into the United States for the purposes of the immigration laws if the alien proves to the satisfaction of the Attorney General that his departure to a foreign port or place or to an outlying possession was not intended ...
(emphasis added). In Rosenberg v. Fleuti, 374 U.S. 449, 83 S.Ct. 1804, 10 L.Ed.2d 1000 (1963), the Supreme Court held that departures that were “not intended” under the statutory exception to the entry requirement included “innocent, casual, and brief’ trips abroad. Id. at 461-62, 83 S.Ct. 1804. Olatunji contends that under the Fleuti doctrine he would not have been required to seek “entry” into the United States after his nine day trip to London. Olatunji further contends that he was only [396]*396required to seek “admission” under IIRI-RA' — thereby subjecting himself to removal proceedings — because of his 1994 guilty plea. Neither the district court, the government, nor the dissent disagrees with these contentions. J.A. 203; Respondent’s Br. at 23-24; post at 29 (“Petitioner could have briefly traveled abroad ... without any consequences.”).
The dissent’s observations that “IIRIRA had no effect whatsoever on Petitioner’s plea agreement and no rights Petitioner might have obtained during plea bargaining have been eliminated,” post at 29, do not bear on whether IIRIRA has attached new legal consequences to Olatunji’s plea. Olatunji does not claim that IIRIRA affected the particular terms of his agreement or deprived him of consideration obtained during the bargaining process; rather, he claims IIRIRA has attached new legal consequences to the conviction that resulted from his plea. The dissent does not dispute this contention because it admits that “Petitioner could have briefly traveled abroad in 1994 without any consequences,” post at 29, but that he is now deportable because of IIRIRA’s treatment of his guilty plea. Id.
Accordingly, we conclude that Olatunji has established that IIRIRA is impermis-sibly retroactive because it indisputably attached new legal consequences to his decision to plead guilty.
3.
As the foregoing makes clear, we believe reliance, in any form, is irrelevant to the retroactivity inquiry. To the extent that it could or should be understood as required in order to establish impermissible retroactive effect however, we would insist at most upon objectively reasonable reliance (as opposed to the subjective reliance proposed by the government and the dissent). See, e.g., Ponnapula v. Ashcroft, 373 F.3d 480 (3rd Cir.2004). This said, we must admit that it is unclear to us in what circumstance, if any, the “reasonable reliance” inquiry will (or at least should) yield a conclusion different from that reached under Justice Story’s framework. For it would seem never to be unreasonable for one to rely upon a duly enacted or promulgated law. Whether the Supreme Court was thinking such or not at the time, its decisions in Landgraf send Hughes Aircraft suggest the same, because in both cases the Court acknowledged that the parties had relied little — if any — on the prior statutes, but in both instances held the later enacted statutes to be impermissibly retroactive.
In Ponnapula, the Third Circuit held that IIRIRA’s changes with respect to discretionary waivers under section 212(c) could not be retroactively applied to aliens who had declined plea deals and proceeded to trial, irrespective of those aliens’ subjective reliance. The Third Circuit observed, as we have suggested, that subjective reliance is inconsistent with Supreme Court precedent because the aggrieved parties in Landgraf and Hughes Aircraft could not have made such a showing, id. at 491, and because subjective reliance is inconsistent with “the language of presumption in Landgraf and its progeny.” Id. at 490. The Third Circuit further concluded, as we have concluded, that St. Cyr did not establish a subjective reliance requirement. And it went on to hold that that ease instead imposes a “reasonable reliance” requirement because, inter alia, “the Court’s holding is not limited to those aliens who actually relied on the availability of § 212(c) relief.” Id. at 493 (emphasis in original).
Relying on St. Cyr, Landgraf, Hughes Aircraft, and Martin v. Hadix, 527 U.S. 343, 119 S.Ct. 1998, 144 L.Ed.2d 347 [397]*397(1999), the Third Circuit explained the reasonable reliance requirement as follows:
[Cjourts are to concentrate on the group to whose conduct the statute is addressed — in Landgraf it was employers subject to Title VII; in Hughes Aircraft it was government contractors; in Ha-dix it was attorneys performing prison reform monitoring services; in St. Cyr it was aliens who accepted a plea agreement — with a view to determining whether reliance was reasonable.
Id. The Third Circuit further explained that, consistent with Hughes Aircraft and Landgraf, “reasonable reliance” will frequently be substantially more attenuated than it was in St. Cyr. But, it said,
the fact that an interest may have been attenuated, however, has had little salience in the Supreme Court’s analysis of other retroactivity questions. For example, ex ante it was unlikely that Hughes Aircraft — or any given government contractor — would need to avail itself of a specific defense against a qui tam action; or that USI Film Products — or any given employer subject to Title VII — would find itself accused of discriminatory conduct meriting punitive damages. In neither case would anyone have claimed, ex ante, that the affected companies had anything more than a highly contingent — and thus seriously attenuated — interest in the then-existing state of the law.
Id. at 495.
If it were to govern, Olatunji would of course be entitled to relief under this framework as well. As in St. Cyr, the group to whose conduct 8 U.S.C. § 1101(a)(13)(C) is addressed is aliens, like Olatunji, who accepted a plea agreement prior to IIRIRA’s enactment. The relevant inquiry, then, is whether these aliens, objectively, might have reasonably relied on their continued ability to take brief trips abroad when they pled guilty.
The reliance interest here is no less attenuated than in Hughes Aircraft and Landgraf. As explained in St. Cyr, “[pjlea agreements involve a quid pro quo between a criminal defendant and the government ... In exchange for some perceived benefit, defendants waive several of their constitutional rights (including the right to trial) and grant the government numerous ‘tangible benefits.’ ” St. Cyr, 533 U.S. at 321, 121 S.Ct. 2271. In addition to the preceding, aliens entering plea agreements forgo the possibility of prevailing at trial and thereby avoiding conviction. Moreover, “there can be little doubt that, as a general matter, alien defendants considering whether to enter into a plea agreement are acutely aware of the immigration consequences of their convictions.” Id. Thus, an alien, like Olatunji, could reasonably have considered the ramifications of his guilty plea on his immigration status, including its implications for travel abroad.
This is not merely hypothetical. Olatun-ji’s plea immediately limited his ability to engage in travel other than that permitted by the Fleuti doctrine. Brief for Petitioner at 31; 8 U.S.C. § 1182(a)(2)(A)(i)(I). Under St. Cyr, “there can be little doubt” that defendants in Olatunji’s position would have been “acutely aware” of these pre-IIRIRA “immigration consequences of their convictions” with respect to travel. At a minimum, aliens who accepted a plea agreement prior to IIRIRA could reasonably have relied on their continuing ability to take brief trips abroad.
The dissent claims that this reliance interest is defeated because “Petitioner could have briefly traveled abroad in 1994 without any consequences whether he was acquitted of theft of government property, pled guilty to the theft of government [398]*398property, or convicted by jury of theft of government property.” Post at 29. While an accurate statement of fact — and an illustration of the retroactive effect of IIRI-RA — this observation does not address the reality that Olatunji and other similarly situated aliens could reasonably have understood their plea agreements as a limitation on their ability to travel abroad rather than an outright prohibition. That some of these aliens, if faced with IIRI-RA’s effective ban on foreign travel, might have elected to go to trial is no less attenuated than the notion that the defendants in Landgraf would have altered their already illegal conduct in the face of increased compensatory and punitive damages.
B.
In addition to arguing that Olatunji’s claim must fail because he has not established subjective reliance, the government maintains that IIRIRA is not impermissibly retroactive because it was enacted prior to Olatunji’s decision to travel abroad and that he therefore should have been on notice of its requirements. Respondent’s Br. at 27-28. The district court adopted this reasoning when it held that “the 1996 IIRIRA amendment has been applied prospectively to events occurring post-enactment,” namely Olatunji’s decision to travel abroad. J.A. 204.
But Olatunji does not claim that IIRIRA is impermissibly retroactive as to his decision to travel abroad; rather, he contends IIRIRA is retroactive as to his decision to plead guilty. Moreover, the fact that Olatunji should have discontinued all foreign travel after IIRIRA’s enactment merely confirms its retroactive effect on his guilty plea. Olatunji had no notice at the time of his plea that Congress would subsequently decide to effectively prohibit him from traveling abroad. Notification is only relevant to the extent that it provides a party an opportunity to avoid future consequences, not as a warning that the government has attached new costs to past conduct.
This conclusion is consistent with Supreme Court and Circuit authority holding that statutes do not have a retroactive effect when a party has an opportunity to avoid all of its new consequences. See Martin v. Hadix, 527 U.S. 343, 119 S.Ct. 1998, 144 L.Ed.2d 347 (1999)(holding that section 803(d)(3) of the Prison Reform Litigation Act (“PLRA”), which caps attorney’s fees awarded pursuant to 42 U.S.C. § 1988, applied exclusively to services performed after the enactment of the PLRA because “[i]f the attorney does not wish to perform services at this new, lower pay rate, she can choose not to work. In other words ... the PLRA has future effect on future work; this does not raise retroactivity concerns”); Velasquez-Gabriel, 263 F.3d 102, 109-10 (holding that IIRIRA was not retroactive because Velasquez-Gabriel had ample opportunity to apply for a status adjustment under pre-IIRIRA law, including the six months between IIRI-RA’s enactment [when — according to the dissent — he would have been on notice] and its effective date).
IV.
The Supreme Court has repeatedly counseled that the judiciary is to presume that Congress, unless it has expressly stated otherwise, does not intend its statutes to operate retroactively. As even the government and the dissent concede, IIRIRA unmistakably had a retroactive effect on Olatunji’s 1994 guilty plea. Because reliance, and particularly subjective reliance, is not required to establish impermissible retroactivity, we hold that this retroactive effect was impermissible. Because the government’s “notice” could not have, and did not, negate this impermissible effect, [399]*399Olatunji is entitled to the relief he seeks. Accordingly, the judgment of the district court is reversed.
REVERSED