Judge OAKES concurs in part and dissents in part in a separate opinion.
JOSÉ A. CABRANES, Circuit Judge.
This case presents a number of complicated issues under the Equal Access to Justice Act, 28 U.S.C. § 2412, (“EAJA”), including a question of first impression in the Courts of Appeals: whether a petition for a writ of habeas corpus challenging an immigration detention qualifies as a “civil action” for the purposes of the EAJA. The EAJA provides that courts shall award fees and other expenses to parties who prevail in civil actions brought by or against the United States unless the position of the Government is substantially justified. 28 U.S.C. § 2412(d)(1)(A). Petitioner Tullio Vacchio (“Vacehio”) filed a habeas petition seeking to be released on bail during the pendency of his removal case. A panel of this Court released Vac-[665] chio on bail and an Immigration Judge later granted his application for cancellation of removal — a decision the Immigration and Naturalization Service (“INS”) did not appeal.1 Vacchio then petitioned for fees and costs under the EAJA. The District Court denied Vacchio’s EAJA petition because it found that he met none of the requirements of the statute — that the case was not a “civil action,” that Vacchio was not a “prevailing party,” and that the position of the United States was “substantially justified.” Although we conclude that the case is a civil action and that Vacchio was a prevailing party, we affirm the judgment of the District Court because the position of the United States was substantially justified.
BACKGROUND
We recount the story of one of those complex immigration proceedings that occur all too frequently, to the embarrassment of all concerned.
Vacchio is a citizen of Italy and permanent resident of this country, and has been here since 1970, when he was 5 years old. In November 2001, he moved from New York to Vermont. Vermont police were notified of Vacchio’s move because he was on probation, having twice been convicted in New York, in 1992 and again in 1999, of Criminal Sale of Marijuana in the Fourth Degree, a misdemeanor under New York Penal Law § 221.40. The Vermont police in turn notified the INS of Vacchio’s move. On September 7, 2002, the INS detained Vacchio pursuant to 8 U.S.C. § 1226(c), claiming he was removable because he had been twice convicted of a drug offense, and his drug convictions constituted “aggravated felonies.”
On September 16, 2002, the Immigration Judge (“IJ”) presiding over the removal action heard Vacchio’s request for redeter-mination of his interim detention. The IJ concluded that the misdemeanor marijuana convictions did not constitute aggravated felonies under federal law, and determined that Vacchio was eligible to apply for discretionary relief because he was a longtime permanent resident and had not been convicted of an aggravated felony. The hearing on Vacchio’s application for cancellation of removal was scheduled for February 11, 2003.
Later that same day, the IJ conducted a bond hearing and concluded that Vacchio should be released on a $2500 bond during the pendency of his removal case. The IJ based her decision on her determination that Vacchio was not subject to mandatory detention and her findings that Vacchio did not pose a risk to the community and was not likely to flee. The INS did not contest these findings but did contend that Vac-chio remained subject to mandatory detention.
The next day, September 17, 2002, the INS filed with the Board of Immigration Appeals (“BIA”) a Form EOIR-43 (“Notice of Intent to Appeal Custody Redeter-mination”) and claimed that the filing of this form effectuated an automatic stay of the IJ’s order releasing Vacchio on bond.2 [666] Consistent with this claim, the INS retained Vacchio in custody. On September 20, 2002, Vacchio filed with the BIA and the IJ an opposition to the INS’s claim of an automatic stay of the order releasing him on bond. The BIA would not consider the filing because, while the INS had filed its notice of intent to appeal, it had not yet actually filed the notice of appeal. In turn, on September 30, 2002, the IJ ruled that she had no jurisdiction to consider Vac-chio’s motion to lift the automatic stay because the INS’s filing of the Form EOIR-34 with the BIA deprived her of jurisdiction pending the BIA’s decision.
The INS filed a “Notice of Appeal from a Decision of an Immigration Judge” with the BIA on October 4, 2002, claiming that the IJ had no authority to release Vacchio on bond because his convictions qualified as aggravated felonies and detention was thus mandatory.
The IJ held a preliminary hearing regarding the merits of the charges underlying the removal proceedings on October 7, 2002. The IJ sustained the controlled substances charges as a proper basis for removal, but rejected the aggravated felony charge, leaving Vacchio eligible for discretionary relief.
On October 8, 2002, Vacchio filed with the BIA a Motion for Lift of Stay and Affirmance of the IJ’s Bond Ruling.3 On November 5, 2002, with no action forthcoming from the BIA, he filed a Petition for Writ of Habeas Corpus in the United States District Court for the District of Vermont, seeking to be released from detention based on his claim that the mandatory detention statute was unconstitutional. The INS opposed the petition, arguing that Vacchio had no chance of avoiding removal because he was an aggravated felon and ineligible for discretionary relief. On December 20, 2002, Judge J. Garvan Murtha found that the habeas petition was premature and dismissed the petition without prejudice. Vacchio then filed a Petition for Writ of Mandamus with the District Court on December 23, 2002, seeking to compel the BIA to rule on the bond appeal.
On January 9, 2003, Vacchio appealed the District Court’s dismissal of his habeas petition to this Court. He also requested that he be released from INS custody pending his appeal of the denial of his habeas petition.
On January 16, 2003, more than three months after the INS filed its notice of appeal, the BIA issued a briefing schedule for the bond appeal, directing the parties to file briefs on February 6, 2003. This schedule was meaningless, as the parties had already filed briefs with their initial filings.
On February 5, 2003, a panel of this Court ordered Vacchio released on bail pending appeal from the denial of his ha-beas petition. Vacchio posted the bond and was released from INS custody that day.
The IJ held a hearing on February 11, 2003, on the merits of Vacchio’s application for cancellation of removal. The IJ granted the application and cancelled the removal. The INS chose not to appeal the [667] IJ’s decision. Subsequently, on February 21, 2003, the INS filed with the BIA a motion to dismiss the bond appeal in light of the IJ’s ruling and advised the BIA that it would not appeal the IJ’s decision. The BIA granted the INS’s motion. On March 13, 2003, Vacchio moved to dismiss his Second Circuit habeas appeal on grounds of mootness, and requested that we vacate the District Court’s decision dismissing the habeas petition. On April 28, we granted the rulings requested.
One month later, on May 28, 2003, Vac-chio filed in the District Court a petition for fees and costs under the EAJA based on his attempts to be released on bond pending the ultimate decision on removal. The Court denied the request. That denial is the basis of this appeal.
DISCUSSION
The Equal Access to Justice Act, 28 U.S.C. § 2412, provides, in relevant part:
Except as otherwise specifically provided by statute, a court shall award to a prevailing party other than the United States fees and other expenses, in addition to any costs awarded pursuant to subsection (a), incurred by that party in any civil action (other than cases sounding in tort), including proceedings for judicial review of agency action, brought by or against the United States in any court having jurisdiction of that action, unless the court finds that the position of the United States was substantially justified or that special circumstances make an award unjust.
28 U.S.C. § 2412(d)(1)(A) (emphasis added).
Three of these provisions are at issue in this case: first, whether the underlying-action is a “civil action” for the purposes of the EAJA; second, whether Vacchio is a “prevailing party” given the disposition of the case; and third, whether the position of the United States was substantially justified. The District Court decided all three issues in favor of the Government. In order to reverse, and grant Vacchio any award, we must decide all three of these issues in his favor. We will examine each of these questions in turn.
A. “Civil Action”
The District Court concluded that Vacchio’s habeas petition for a release from immigration detention did not qualify as a “civil action” under the EÁJA. As this question “presents only a legal issue of statutory interpretation,” we review the District Court’s holding de novo. Perry v. Dowling, 95 F.3d 231, 235 (2d Cir.1996).
As noted, the EAJA applies to “any civil action (other than cases sounding in tort), including proceedings for judicial review of agency action, brought by or against the United States in any court having jurisdiction of that action.” 28 U.S.C. § 2412(d)(1)(A). On its face, the term “any civil action” would seem to include habeas petitions, which ordinarily qualify as civil actions. See, e.g., Zadvydas v. Davis, 533 U.S. 678, 690, 121 S.Ct. 2491, 150 L.Ed.2d 653 (2001) (noting, in a case stemming from a habeas petition challenging immigration detention, that “[t]he proceedings at issue here are civil, not criminal”). However, “[wjhile it is true that a habeas corpus proceeding is civil in nature, it is equally true that such a proceeding is dramatically different from any other type of civil action.” Brown v. Vasquez, 952 F.2d 1164, 1169 (9th Cir.1991) (internal citation omitted). Accordingly, we must determine whether the limitation to “civil actions” excludes from the statute’s ambit habeas proceedings challenging immigration detentions. See In re Grand Jury Subpoena Duces Tecum Dated January 2, 1985 (Simels), 775 F.2d 499, 503 (2d Cir.1985) (“The application of each statute or rule using the words ‘civil action’ must be [668] decided on the basis of its language, its history and its purpose.”)- So far as we can tell, this specific question has never been squarely decided by any court.
The question requires us to consider our decision in Boudin v. Thomas, 732 F.2d 1107 (2d Cir.1984) a case involving an EAJA petition based on a successful 42 U.S.C. § 1983 action that we characterized as having been in the nature of a habeas petition. We there stated: “We ... consider whether habeas petitions are ‘civil actions’ under section 2412. We hold that they are not.” Id. at 1112. In so deciding, we recognized the ambiguity arising from the fact that “habeas actions are civil for some purposes but not others,” and referred to the legislative history of the EAJA to resolve the ambiguity. Id. We noted that there were two stated purposes to the EAJA: (1) to remove financial deterrents for those challenging government actions, id. at 1112-13 (“The EAJA was passed in part to ensure that certain individuals, partnerships, corporations and other organizations would not be deterred from contesting unreasonable government action simply because the amount of money involved would not make hiring a private attorney cost effective.”); and (2) to encourage challenges to improper government actions and help formulate public policy. Id. at 1114 (“The EAJA was passed partly to encourage challenges to improper actions by government agencies. The drafters perceived legal actions as helping to formulate public policy ....”) (emphasis omitted). We concluded that applying the EAJA to criminal habeas petitions furthered neither of those goals, and that habeas claims were therefore not intended to be included in the term “civil actions” under the EAJA. Id. at 1114-15; see also In re Grand Jury Subpoena Duces Tecum, 775 F.2d at 502-04 (following Boudin in holding that motion to quash a grand jury subpoena is not a “civil action” for the purposes of the EAJA).
The holding of Boudin remains good law in this Circuit and the Government forcefully argues that it is dispositive of this case. The District Court agreed and held accordingly.
Vacchio argues in response that Boud-in’s holding only encompassed habeas petitions in the criminal context and thus should not apply to habeas petitions in the immigration context. The word “immigration” and its related terms are nowhere found or discussed within the Boudin opinion and there is no reason to think that immigration proceedings were in any way considered in deciding that case. We must thus decide whether the holding of Boudin governs this case, or can be limited to the criminal context in which it arose.
We hold today that Boudin’s holding— that the EAJA term “civil actions” does not apply to habeas petitions — is limited to criminal habeas petitions. In the absence of controlling precedent from Boudin (since Vacchio’s habeas petition was not in the criminal context) we furthermore hold that “civil actions” under EAJA encompass immigration habeas petitions. In reaching this conclusion, we consider (1) post-Boudin case law of this Court and others, and (2) the legislative history of EAJA, focusing on Congress’s aims in enacting the statute and the question whether interpreting “civil actions” to include immigration-context habeas petitions is consistent with those aims.
We have previously suggested, in post-Boudin opinions, that Boudin might in fact be so limited. In Hashim v. INS, 936 F.2d 711 (2d Cir.1991), a case holding that EAJA relief is not available to a party prevailing in an INS exclusion proceeding (not a habeas proceeding, but the underlying exclusion proceeding before the BIA), we noted in a footnote that “[w]e did suggest in Oguachuba v. INS, 706 F.2d 93, 98 (2d Cir.1983), a habeas corpus proceeding, that an alien might recover attorneys’ fees [669] under the EAJA as a prevailing party against the INS in a civil action. We noted that Congress has defined ‘civil action’ broadly, specifically exempting ‘cases sounding in tort,’ and ‘including proceedings for judicial review of agency action.’ ” Id. at 714 n. 3 (quoting 28 U.S.C. § 2412(d)(1)(A)).4 This observation, coming seven years after Boudin, suggests that Boudin is not necessarily dispositive for all habeas proceedings.5
We did not address this question in Sotelo-Aquije v. Slattery, 62 F.3d 54 (2d Cir.1995), a case involving an EAJA petition based on a successful appeal to this Court of the denial of a habeas petition stemming from a BIA denial of asylum. We merely concluded there that the Government’s position in the underlying litigation was not “substantially justified” and reversed the denial of fees and costs under the EAJA. Id. at 55. That opinion never mentioned Boudin or the civil action issue at all and the Court does not seem to have questioned that the EAJA applied to the case. Yacchio argues that this is an implicit recognition that Boudin does not apply to habeas petitions challenging immigration proceedings.
The Ninth Circuit has explicitly declined to follow Boudin in a case presenting an EAJA request based on a successful habe-as petition challenging an INS exclusion. In re Hill, 775 F.2d 1037 (9th Cir.1985). The Hill Court concluded that the considerations advanced in Boudin do not apply identically in the immigration context as in the criminal context, noting that aliens, unlike criminal defendants, are not eligible for government-provided counsel (and thus have greater need for a financial incentive), and that immigration claims often present not merely a vindication of the petitioner’s personal rights, “but a challenge to a regulatory policy,” and thus better serve the goal of formulating public policy. Id. at 1040-41. The Hill holding has been followed by one District Court in this Circuit, see Toutounjian v. INS, 2 F.Supp.2d 374 (W.D.N.Y.1998), also in the context of a habeas challenge to an exclusion proceeding.
This review demonstrates that post-Boudin judicial opinions, both by this Court and others, do not directly address the present question, but at the very least do not suggest that the Boudin holding be read expansively. In light of the ambiguity of the term “civil action,” and the indeterminacy of the existing precedent, we now examine the legislative history of the EAJA.
The primary source for the legislative history on the EAJA is the House of Representatives Report on the bill. H.R.Rep. No. 96-1418 (1979), reprinted in 1980 U.S.C.C.A.N. 4984.6 In assessing the legislative history, the Boudin Court focused on the House Report’s statement that “[f]or many citizens, the costs of securing vindication of their rights and the inability to recover attorney fees preclude resort to the adjudicatory process. When the cost of contesting a Government order, for example, exceeds the amount at stake, a party has no realistic choice and no effec[670] tive remedy. In these cases, it is more practical to endure an injustice than to contest it.” 732 F.2d at 1113 (quoting H.R.Rep. No. 96-1418 at 5 (citation omitted), reprinted in 1980 U.S.C.C.A.N. at 4988). Based on this and similar language in the legislative history, Boudin concluded that “unlike civil litigation against the government, there is no need for financial encouragement of habeas proceedings,” because when liberty is at stake, the costs will not serve as a deterrent, and there is no consideration of financial gain because “a habeas petition is not financial litigation.” 732 F.2d at 1113. In effect, Boud-in seems to have understood the financial encouragement purpose of the EAJA as a means of limiting the term “civil action” to those cases where financial encouragement was necessary.7
However, we have not held that the purpose of the EAJA to provide a financial incentive means that the statute can apply only to litigation entered into by choice and not to litigation where the non-government party is essentially forced to participate. Indeed, the Supreme Court has suggested otherwise. See Ardestani v. INS, 502 U.S. 129, 138, 112 S.Ct. 515, 116 L.Ed.2d 496 (1991) (“The clearly stated objective of the EAJA is to eliminate financial disincentives for those who would defend against unjustified governmental action and thereby deter the unreasonable exercise of Government authority.”); see also SEC v. Price Waterhouse, 41 F.3d 805, 809 (2d Cir.1994) (Leval, J., dissenting in part) (“The provisions of the EAJA, despite its somewhat misleading name, are designed to compensate victims of unjustified litigation by the Government from some of the burdensome expenses and costs to which they were subjected by the Government’s taking of unreasonable positions.... The Act essentially recognizes that abusive litigation tactics by the United States government, whether the Government appears in the role of plaintiff or defendant, can inflict great unjustifiable cost and expense. It is designed to furnish relief from such governmental litigation abuse.”) (emphasis omitted). We have not doubted that, in appropriate circumstances, the EAJA’s application to civil actions would encompass, for example, a situation where the SEC takes legal action against an individual who is then forced to engage counsel to defend himself. Cf id. (holding that petitioner could not get EAJA relief for underlying SEC action because he had appeared pro se and therefore did not have any attorney’s fees or costs). In such situations there is no need for an additional financial encouragement, but the EAJA still applies “to compensate victims of unjustified litigation” by the Government. See id. (emphasis omitted). The financial incentive purpose is thus somewhat underinclusive when employed as a means of defining “civil action” and is not dispositive as to the scope of the EAJA’s coverage.
In distinguishing habeas petitions challenging immigration detentions from habe-as petitions in the criminal context, we also note, along with the Ninth Circuit in Hill, that unlike criminal defendants, persons in immigration proceedings are not provided with legal counsel. 775 F.2d at 1041; see 8 U.S.C. § 1362 (“In any removal proceedings before an immigration judge and in any appeal proceedings before the Attorney General from any such removal proceedings, the person concerned shall have the privilege of being represented (at no expense to the Government) by such counsel, authorized to practice in such proceedings, as he shall choose.”) (emphasis add[671] ed). The required appointment of counsel for criminal defendants was relied on by the Boudin Court as a large part of the rationale for its conclusion that financial encouragement was unnecessary in habeas actions in the criminal setting and that habeas actions therefore did not constitute “civil action[s]” under the statute. 732 F.2d at 1113-14. Because persons in immigration proceedings are not provided free legal representation in the absence of paid counsel, that rationale is not nearly as persuasive in this context as it was in the criminal context addressed by the Boudin Court. We conclude that the EAJA’s purpose of providing financial encouragement to litigants is not sufficient to demonstrate that Congress’ intent was to exclude habe-as petitions in the immigration context from the term “civil action[s].”8
The rationale of encouraging challenges to improper government action as a means of formulating better public policy rather than vindicating individual rights is well addressed by applying EAJA to these particular habeas proceedings.9 The issue raised by Vacchio — a challenge to the constitutionality of the mandatory detention statute — is not a question of fact particular to his case; it is a question regarding the validity of a regulatory policy that affects numerous people. It is clear that this and similar proceedings in this context can “providef] a concrete, adversarial test of Government regulation and thereby insure[] the legitimacy and fairness of the law.” Boudin, 732 F.2d at 1114 (quoting H.R.Rep. No. 96-1418, at 6, reprinted in 1980 U.S.C.C.A.N. 4984, 4989).10
[672] We note, in closing, that our holding that the EAJA term “civil actions” includes immigration habeas petitions conforms to the larger scheme of the EAJA. The EAJA provides attorney’s fees only for civil actions. Boudin excepted from this provision criminal habeas petitions— in essence, denying relief to those who bring a collateral civil action (habeas) that has its roots in a criminal action. This is not the case in the context of an immigration habeas petition, which is both a civil action in its own right, and which has its roots in a civil action.
Accordingly, we limit the Boudin holding to the criminal context presented by that case, and hold that a habeas proceeding challenging immigration detentions constitutes a “civil action” under the EAJA.
B. “Prevailing Party”
The District Court concluded that Vacchio was not a “ ‘prevailing party’ for the purpose of awarding costs and fees against the United States.” The Court reasoned that Vacchio “claimed the mandatory detention statute, and the automatic stay regulation which resulted in his continued detention despite the IJ’s grant of bond, violated due process. This District Court dismissed the petition as premature, and the Court of Appeals, while releasing him on bail pending the outcome of the merits of his appeal, did not address the constitutional issues he raised. In administrative proceedings, the petitioner ultimately obtained the relief he sought: retention of his lawful permanent resident status.” Like the “civil action” question, the question of whether Vacchio prevailed in his action is a legal issue, and we review it de novo. Pres. Coalition of Erie County v. FTA, 356 F.3d 444, 450 (2d Cir.2004).
The determination of whether Vacchio has “prevailed” turns on the accurate characterization of the claim upon which he sought to prevail. Though Vacchio was trying to retain his permanent resident status in the underlying immigration proceeding, in the habeas petition itself— which is the sole or principal basis for the EAJA request — he clearly identifies the relief he seeks: “a writ of habeas corpus releasing him from unlawful and unconstitutional detention by the [INS].” His claim is premised entirely on the asserted unconstitutionality of the mandatory detention statute - and the automatic stay regulations as applied to his particular circumstances because they required his detention “during the pendency of his removal case.” We note also that the legal bills submitted with the EAJA request were solely for the period following September 17, 2002, during which the INS prevented Vacchio from being released on bond as the IJ had ordered. We therefore disagree with the District Court’s characterization of the relief Vacchio sought as “retention of his lawful permanent resident status” and instead identify the relief sought as the release on bond by courts of the United States pending determination of his removal case. It is with regard to the claim for that relief that we analyze whether Vacchio “prevailed.”
The Government argues that Vacchio could be considered a prevailing party only if we had adjudicated his constitutional argument on the merits and struck down the mandatory detention regulation. We discussed this question in Haley v. Pataki, 106 F.3d 478 (2d Cir.1997), and noted [673] there that “[w]hile we have ruled that the grant of a stay or injunction pending appeal is not necessarily relief on the merits which entitles a plaintiff to attorney’s fees, we do not automatically require denial of attorney’s fees when a party receives a stay or preliminary injunction but never obtains final judgment.” Id. at 483 (internal citation omitted). We held that “a decision to award attorney’s fees requires an analysis of whether the party’s relief, whether by injunction or stay, resulted from a determination of the merits. When a party receives a stay or preliminary injunction but never obtains a final judgment, attorney’s fees are proper if the court’s action in granting the preliminary injunction is governed by its assessment of the merits.” Id. (internal citation omitted).
Preliminarily, we note that Haley predates the Supreme Court’s opinion in Buckhannon Bd. & Care Home, Inc. v. W. Va. Dep’t of Health & Human Res., 532 U.S. 598, 121 S.Ct. 1835, 149 L.Ed.2d 855 (2001) and its holding that a party can be found to prevail when there is a “material alteration of the legal relationship of the parties.” Id. at 604, 121 S.Ct. 1835 (quoting Tex. State Teachers Ass’n v. Garland Indep. Sch. Dist., 489 U.S. 782, 792-93, 109 S.Ct. 1486, 103 L.Ed.2d 866 (1989)). Accordingly, we do not limit the Haley holding to the granting of a stay or preliminary injunction, but understand it to apply to any interim judicial relief that alters the parties’ legal relationship. We thus conclude that Haley applies to the present case, which involves a court order directing that Vacchio be released on bail, rather than a stay or a preliminary injunction.
Our order granting Vacchio’s motion to be released on bail pending appeal considered whether “(1) the petitioner raises a substantial claim for relief, and (2) ‘extraordinary circumstances exist [ ] that make the grant of bail necessary to make the habeas remedy effective.’ ” (quoting Mapp v. Reno, 241 F.3d 221, 230 (2d Cir.2001)) (alteration in original). We determined that both elements were “plainly met,” acknowledging that Vacchio’s claim on the merits involved “a number of substantial constitutional and statutory issues” and that the circumstances of the case were sufficiently extraordinary to make bail necessary.
The order was thus similar to the underlying order in the Haley case, where the District Court granted the plaintiffs a preliminary injunction based on “a strong showing of irreparable harm and a likelihood of success on the merits.” 106 F.3d at 483 (internal quotation marks omitted). The extraordinary circumstances found in the instant case are analogous to a showing of irreparable harm, and, though the analyses are distinct, our finding that Vac-chio had “a substantial claim for relief’ demonstrates a consideration of the merits — otherwise, we would not have released him. See id. (“[T]he district court’s decision to issue the injunction was clearly based on the likelihood of the plaintiffs success on the merits.”). We thus conclude, following Haley, that our decision releasing Vacchio on bail involved an assessment of the merits..
.The Government suggests that the Supreme Court’s language in Buckhannon indicates that Vacchio cannot be considered a prevailing party, but the holding of that case and its offspring suggest otherwise. The Supreme Court summarized the issue: “Numerous federal statutes allow courts to award attorney’s fees and costs to the ‘prevailing party.’ The question presented here is whether this term includes a party that has failed to secure a judgment on the merits or a court-ordered consent decree, but has nonetheless achieved the desired result because the lawsuit brought about a voluntary change [674] in the defendant’s conduct. We hold that it does not.” 532 U.S. at 600, 121 S.Ct. 1835 (emphasis added). Construing this decision recently, we held that “Buckhan-non does not limit fee awards to enforceable judgments on the merits or to consent decrees. While these orders were cited by the Court as examples of the types of actions that would convey the judicial imprimatur necessary to a fee award, broader language in Buckhannon indicates that these examples are not an exclusive list. Rather, as noted, Buckhannon states that status as a prevailing party is conferred whenever there is a ‘court ordered chang[e][in] the legal relationship between [the plaintiff] and the defendant’ or a ‘material alteration of the legal relationship of the parties.’ ” Pres. Coalition, 356 F.3d at 452 (quoting 532 U.S. at 604, 121 S.Ct. 1835).
The case before us presents anything but a “voluntary change in the defendant’s conduct.” Buckhannon, 532 U.S. at 600, 121 S.Ct. 1835. The Government sought to keep Vacchio in detention during the pendency of the appeal, and succeeded in doing so until the Court of Appeals ordered him released on bail. That ruling by this Court, which, as noted above, involved an assessment of the merits, unquestionably materially altered the existing legal relationship between the parties, and thus sufficed to confer prevailing party status.11 See also Select Milk Producers, Inc. v. Veneman, 304 F.Supp.2d 45, 52 (D.D.C.2004) (finding “two separate reasons” why the plaintiffs could be a prevailing party despite obtaining only a preliminary injunction: “first, the preliminary injunction in this case did create a material alteration in the legal relationship between the parties as required under Buck-hannon,” and “[s]econd, the change in the parties’ legal relationship that resulted from the preliminary injunction was the exact relief that plaintiffs sought”), affirmed in relevant part, 400 F.3d 939, 942 (D.C.Cir.2005).
Accordingly, we conclude that Vacchio is a prevailing party under the statute.
C. “Substantially Justified”
The Supreme Court has defined the term “substantially justified” as “justified in substance or in the main — that is, justified to a degree that could satisfy a reasonable person.” Comm’r of INS v. Jean, 496 U.S. 154, 158 n. 6, 110 S.Ct. 2316, 110 L.Ed.2d 134 (1990) (internal quotation marks omitted). We have held that the Government must demonstrate that its position “had a reasonable basis in both law and fact.” Sotelo-Aquije, 62 F.3d at 57 (internal quotation marks omitted). The District Court concluded that the position of the Government in this case was substantially justified for two reasons: first, because the Government’s position that Vacchio was an aggravated felon subject to mandatory detention was reasonable, even though the IJ eventually found against the Government; and second, because the Government’s argument that the mandatory detention statute and automatic stay regulation were constitutional was reasonable as well, under the Supreme Court’s holding in Demore v. Kim, 538 U.S. 510, 526, 123 S.Ct. 1708, 155 L.Ed.2d 724 (2003) (holding that “the Government may constitutionally detain deportable aliens during the limited period necessary for their removal proceedings”). Vacchio challenges each of these grounds for the District Court’s holding and additionally [675] argues that the District Court erred in failing to consider whether the BIA was substantially justified in delaying its ruling on appeal of the bond issue for over five months.
We review the District Court’s finding that the Government has met its burden of demonstrating its position was substantially justified for abuse of discretion. Pierce v. Underwood, 487 U.S. 552, 562, 108 S.Ct. 2541, 101 L.Ed.2d 490 (1988). An error of law by the District Court constitutes an abuse of discretion. Zervos v. Verizon N. Y., Inc., 252 F.3d 163, 168-69 (2d Cir.2001).
The EAJA defines “position of the United States” as “in addition to the position taken by the United States in the civil action, the action or failure to act by the agency upon which the civil action is based.” 28 U.S.C. § 2412(d)(2)(D). Pursuant to this definition, the relevant position of the United States, for the purpose of assessing substantial justification, is the INS’s effort in the courts to deny Vacchio release on bond pending the ultimate determination of removal by the IJ. We thus analyze this position as to both law and fact, with regard to both the underlying legal position (that Vacchio was an aggravated felon subject to mandatory detention) and the specific legal position taken in the habeas action (that the mandatory detention statute was constitutional in the circumstances presented).
We hold that the legal position taken by the Government in response to the habeas petition was substantially justified. Whatever the merits of the INS’s decision to deny Vacchio release on bond, there is no doubt that the Government is entitled — if not obligated — to put forth a good faith effort to defend the constitutionality of federal laws, especially those that have never been found unconstitutional. Vac-chio makes an arguable case that the holding of Demore, 538 U.S. at 526-31, 123 S.Ct. 1708, should be limited to those already found deportable or who have conceded deportability. His argument is bolstered by dicta from a recent Seventh Circuit opinion, Gonzalez v. O’Connell, 355 F.3d 1010, 1019-20 (7th Cir.2004), and the published opinions of three District Courts that have found the automatic stay regulation unconstitutional in circumstances analogous to those in this case. Ashley v. Ridge, 288 F.Supp.2d 662 (D.N.J.2003); Uritsky v. Ridge, 286 F.Supp.2d 842 (E.D.Mich.2003); Bezmen v. Ashcroft, 245 F.Supp.2d 446 (D.Conn.2003). However, although some non-binding precedents do support Vacchio’s position, the issue is far from settled law, the Government’s legal argument is far from unreasonable, and it thus cannot be said that the Government’s position on the question is not substantially justified.
On the aggravated felon question, the Government’s position is that Vacchio’s two New York State convictions for criminal sale of marijuana in the fourth degree, in violation of New York Penal Law Section 221.40, make him guilty of an “aggravated felony” under federal law because they would be punishable under federal law by imprisonment of more than one year. Though the law on this issue is not perfectly clear, there is ample authority that the INS is not unreasonable in this characterization. See, e.g., United States v. Simpson, 319 F.3d 81, 85 (2d Cir.2002) (holding that “a drug trafficking offense is an ‘aggravated felony’ when it is: (1) an offense punishable under the [Controlled Substances Act], and (2) can be classified as a felony under either state or federal law” and concluding that conviction under New York Penal Law Section 221.40 thus qualified as “aggravated felony” under the Sentencing Guidelines) (emphasis omitted); Copeland v. Ashcroft, 246 F.Supp.2d 183, 187-89 (W.D.N.Y.2003) (discussing Second Circuit law on this question and following Simpson to find that misdemeanor convictions under New York law can constitute [676] “aggravated felonies” if they would be considered felonies under federal law).
Vacchio relies on the Third Circuit’s-decision in Steele v. Blackman, 236 F.3d 130 (3d Cir.2001), a case with similar facts, as did the IJ in reaching her ultimate decision on the merits:
One cannot suffer the disabilities associated with having been convicted of an aggravated felony unless one has been convicted of a felony. This, of course, means that there must be a judicial determination beyond a reasonable doubt of every element of a felony or a constitutionally valid plea that encompasses each of those elements.... The fact that this hypothetical offense approach imposes such grave consequences on factual determinations made, or pleas entered, in misdemeanor proceedings is one of its more troubling aspects. Misdemeanor charges are frequently not addressed by a defendant with the same care and caution as a felony indictment with its more serious, immediate consequences. This concern counsels, at a minimum, that we insist on sufficient formality in the misdemeanor proceeding to assure that each and every element of the hypothetical federal felony is focused on and specifically addressed in that proceeding.
Id. at 136-37 (emphasis omitted). Vacchio argues that Steele is relevant because the New York law in question does not include a remuneration element, and the elements of drug trafficking under federal law are thus not present.12 The Government argues in response that Steele is not controlling authority, and further notes that it is prepared to introduce evidence that Vac-chio did receive remuneration. In light of this history, and despite Vacchio’s citation of various cases to the contrary, we hold that the Government’s legal position was substantially justified by the existing precedent.13
Finally, Vacchio argues that there was no justification for the BIA’s failure to decide the appeal within a reasonable period, and that “[e]ven if the constitutional and statutory issues involved in the habeas petition were fairly debatable, the delay of the BIA was not.” Though anyone might understand Vacchio’s frustration at the BIA’s delay in this case, his habeas petition is directed at the INS, the agency detaining him, and it is the actions of the INS in this case that constitute the “position of the United States.”14
[677] As a result, we conclude that the Government’s position in this case is substantially justified, and Vacchio therefore has not prevailed on all three requirements for an award of fees and costs under the EAJA. 28 U.S.C. § 2412(d)(1)(A).
Our holding that the position of the United States was “substantially justified” should not be taken to indicate blanket approval of the INS’s actions in this case— which can be characterized as holding Vac-chio in detention for five months based on two misdemeanor convictions for the sale of small amounts of marijuana, while relying on a viable, but far from compelling, legal theory, in a case where the IJ found that there was no risk to the community and no flight risk. Indeed, the INS’s continued insistence that Vacchio was sufficiently threatening to necessitate being indefinitely detained is undermined by its own decision not to appeal his ultimate release, an about-face which makes its actions appear considerably more frivolous and unreasonable than the underlying legal claims reveal them to be. Nonetheless, despite our doubts over the INS’s actions, we are not able to conclude that the Government’s position was not “substantially justified.”
CONCLUSION
For the reasons stated above, we conclude:
1. Habeas petitions challenging immigration detentions,- constitute “civil action[s]” for the purpose of the EAJA.
2. Vacchio was a “prevailing party” on the facts of this case.
3. The position of the United States in this case was “substantially justified.”
Accordingly, Vacchio not having met all of the requirements of the EAJA, the judgment of the District Court is affirmed.