Lazaro Borrero is an inadmissible alien subject to a final order of removal. Because his native country, Cuba, will not accept his return, he was held in the custody of the Immigration and Naturalization Service (INS) upon his release from prison on state drug and firearms charges on September 11, 2000. The district court granted Borrero’s petition for writ of ha-beas corpus, and he was released from INS custody on January 4, 2002. The government appeals, arguing that it has statutory authority to detain inadmissible aliens, indefinitely if necessary, pending deportation. Our decision in this case turns on the application of Zadvydas v. Davis, 533 U.S. 678, 121 S.Ct. 2491, 150 L.Ed.2d 653 (2001), in which the Supreme Court adopted a narrowing construction of 8 U.S.C. § 1231(a)(6) in order to avoid a serious doubt about its constitutionality as applied to admitted aliens. Because the detention of inadmissible aliens does not raise the same constitutional concerns as does the detention of admitted aliens, we conclude that Zadvydas’s narrowing construction of § 1231(a)(6) does not limit the government’s .statutory authority to detain inadmissible aliens. Accordingly, we reverse.
I.
The facts underlying this appeal are undisputed. Borrero is a citizen of Cuba who arrived at the border of the United States in 1980 during the Mariel boatlift. The Immigration and Naturalization Service (INS) paroled Borrero into the United States on June 4, 1980. During his parole, Borrero was convicted of simple battery in 1983, cocaine possession in 1984, and theft from the person in 1987. In 1993, Borrero was convicted of possession and sale of cocaine and possession of a pistol by a felon. While Borrero was in state custody on his 1993 convictions, the INS initiated removal proceedings against him. The immigration judge found Borrero removable and ineligible for asylum or withholding of removal because of his serious criminal offenses. The Board of Immigration Appeals affirmed.
On September 11, 2000, Borrero was released from state custody into the custody of the INS. On September 19, 2000, the INS revoked Borrero’s immigration parole, citing his firearms offense and his threat to kill an immigration judge. In accordance with the parole review procedures for detained Mariel Cubans, 8 C.F.R. § 212.12, the INS reviewed Borre-ro’s parole status in March 2001. On May 1, 2001, after interviewing Borrero and considering various factors weighing for and against parole, the Associate Commissioner was unable to conclude that Borre-ro’s parole would be in the public interest. The district court determined that the Zadvydas narrowing construction of § 1231(a)(6) applied uniformly to both admitted and inadmissible aliens and thus held that, absent a significant likelihood that Borrero “actually will be removed from the United States in the reasonably foreseeable future,” he was entitled to release on parole. As set forth above, the district court granted Borrero’s petition for writ of habeas corpus on January 4, 2002, and ordered that he be released subject to such terms and conditions the INS deemed appropriate pursuant to § 1231(a)(3).
II.
We review the district court’s interpretation of a federal statute de novo. Norwest Bank of North Dakota, N.A. v. Doth, 159 F.3d 328, 332-33 (8th Cir.1998). We give substantial deference to an agency’s interpretation of the statutes and regulations it administers. INS v. Aguirre-Aguirre, 526 U.S. 415, 424, 119 S.Ct. 1439, 143 L.Ed.2d 590 (1999); Vue v. INS, 92 *1006F.3d 696, 699 (8th Cir.1996). If the agency interpretation conflicts with a decision of the Supreme Court, however, we are bound by the Court’s interpretation. See Mesa Verde Constr. Co. v. Northern Cal. Dist. Council of Laborers, 861 F.2d 1124, 1140 (9th Cir.1988).
This case presents the issue of whether the narrowing construction of § 1231(a)(6) applied to admitted aliens in Zadvydas is in conflict with the construction of § 1231(a)(6) the INS would have us apply to inadmissible aliens. In Zadvydas, the Court addressed the government’s statutory authority under § 1231(a)(6) to detain indefinitely “aliens who were admitted to the United States but subsequently ordered removed.” 533 U.S. at 682, 121 S.Ct. 2491. Ordinarily, “the Attorney General shall remove the alien from the United States” within ninety days of the date on which the order of removal becomes final. 8 U.S.C. § 1231(a)(1). However, when an alien’s removal during the ninety-day removal period is not possible, § 1231(a)(6) provides for continued detention of that alien:
An alien ordered removed who is inadmissible under section 1182 of this title, removable under section 1227(a)(1)(C), 1227(a)(2), or 1227(a)(4) of this title or who has been determined by the Attorney General to be a risk to the community or unlikely to comply with the order of removal, may be detained beyond the removal period and, if released, shall be subject to the terms of supervision in paragraph (3).
The aliens ordered removed in Zadvydas were resident aliens who had been ordered removed after they had completed sentences for serious crimes. 533 U.S. at 684-85, 121 S.Ct. 2491. Confronted with a statute that placed no time limit on the detention of aliens within the three specified categories, the Court “interpret[ed] the statute to avoid a serious constitutional threat,” and “conclude[d] that, once removal is no longer reasonably foreseeable, continued detention is no longer authorized by statute.” Id. at 699, 121 S.Ct. 2491. Although acknowledging the primacy of the executive branch in foreign policy matters including immigration and repatriation negotiations, the Court nonetheless recognized a presumptively reasonable detention period of six months. Id. at 700-01, 121 S.Ct. 2491.
Zadvydas framed the issue presented as “whether this post-removal-period statute authorizes the Attorney General to detain a removable alien indefinitely beyond the removal period or only for a period reasonably necessary to secure the alien’s removal.” Id. at 682, 121 S.Ct. 2491. The “serious constitutional problem” raised by a statute that permits indefinite detention stems from the Fifth Amendment’s Due Process Clause prohibition of government detention except as a result of a criminal proceeding conducted with adequate procedural safeguards or “in certain special and ‘narrow non-punitive ‘circumstances’ where a special justification, such as harm-threatening mental illness, outweighs the ‘individual’s constitutionally protected interest in avoiding physical restraint.’ ” Id. at 690, 121 S.Ct. 2491 (citing United States v. Salerno, 481 U.S. 739, 746, 107 S.Ct. 2095, 95 L.Ed.2d 697 (1987); Foucha v. Louisiana, 504 U.S. 71, 80, 112 S.Ct. 1780, 118 L.Ed.2d 437 (1992); Kansas v. Hendricks, 521 U.S. 346, 356, 117 S.Ct. 2072, 138 L.Ed.2d 501 (1997)). Post-removal detention is civil in nature, not criminal, and it applies “broadly to aliens ordered removed for many and various reasons, including tourist visa violations.” Id. at 691, 121 S.Ct. 2491. The Court distinguished Shaughnessy v. United States ex rel. Mezei, 345 U.S. 206, 73 S.Ct. 625, 97 L.Ed. 956 (1953), in which it rejected an alien’s due process challenge to *1007indefinite detention, on the grounds that Mezei had not effected an entry.
The distinction between an alien who has effected an entry into the United States and one who has never entered runs throughout immigration law. It is well established that certain constitutional protections available to persons inside the United States are unavailable to aliens outside of our geographic borders. But once an alien enters the country, the legal circumstance changes, for the Due Process Clause applies to all “persons” within the United States, including aliens, whether their presence here is lawful, unlawful, temporary, or permanent.
533 U.S. at 693, 121 S.Ct. 2491 (citations omitted). Whereas an alien within the country is entitled to the protection of the Due Process Clause, whatever process Congress has authorized will satisfy the Constitution with respect to an alien requesting admission. Landon v. Plasencia, 459 U.S. 21, 33-35, 103 S.Ct. 321, 74 L.Ed.2d 21 (1982) (“[CJontrol over matters of immigration is a sovereign prerogative, largely within the control of the Executive and the Legislature.”); United States ex rel. Knauff v. Shaughnessy, 338 U.S. 537, 544, 70 S.Ct. 309, 94 L.Ed. 317 (1950) (“Whatever the procedure authorized by Congress is, it is due process as far as an alien denied entry is concerned.”). The constitutional issue avoided in Zadvydas is simply not present in the context of aliens who have not effected an entry into the United States.
Borrero argues that when the Supreme Court narrowly construes a statute to avoid constitutional doubt, that construction applies categorically to all future cases whether or not the circumstances raise the same constitutional questions. Although Xi v. INS, 298 F.3d 832, 835-36 (9th Cir.2002), and Rosales-Garcia v. Holland, 322 F.3d 386, 405-06 (6th Cir.2003) (en banc), take this view, we respectfully disagree. We interpret Zadvydas as limiting the detention of only those aliens whose detention raises serious constitutional doubt — admitted aliens. See Xi, 298 F.3d at 841-42 (9th Cir.2002) (Rymer, J., dissenting); see also Chavez-Rivas v. Olsen, 207 F.Supp.2d 326, 337 (D.N.J. 2002) (paraphrasing Zadvydas’s narrowing construction as “an alien may be detained beyond the removal period, and, if the alien is not inadmissible, such detention shall not extend beyond a period reasonably necessary to secure removal.”). Zadvydas itself does not mandate uniform application of § 1231(a)(6) to all aliens. Noting that § 1231(a)(6) applies to “terrorists and criminals,” 533 U.S. at 697, 121 S.Ct. 2491, the Court stated that “terrorism or other special circumstances” may justify greater deference to Congress and the Executive. Id. at 696, 121 S.Ct. 2491. In light of the fact that Zadvydas expressly distinguished Mezei on the grounds that Mezei had not made an entry into the United States, we conclude that Zadvy-das ’s six-month presumption of reasonableness is inapplicable to inadmissible aliens.
Finding no statutory time limit on the detention of an inadmissible alien, we turn to Borrero’s-constitutional argument. Borrero contends that if § 1231(a)(6) authorizes indefinite detention of inadmissible aliens, it is unconstitutional under the Due Process Clause of the Fifth Amendment. However persuasive this argument may be, we are bound by the Supreme Court’s decision in Mezei, which Zadvydas neither overruled nor undermined. Rather, the Zadvydas Court stated that “[ajliens who have not yet gained initial admission to this country would present a very different question.” 533 U.S. at 682, 121 S.Ct. 2491. Like Zadvydas, Mezei involved indefinite detention, but the critical *1008difference was that Mezei had not effected an entry into the United States. Although Mezei was physically present on Ellis Island, “he was ‘treated,’ for constitutional purposes, ‘as if stopped at the border.’ And that made all the difference.” Id. at 693, 121 S.Ct. 2491.
Mezei involved an alien who, after living in the United States for twenty-five years, went abroad for nineteen months. 345 U.S. at 208, 73 S.Ct. 625. Upon his return he was temporarily excluded from the United States by an immigration inspector. Id. On the basis of confidential information and without a hearing, the Attorney General made the exclusion permanent. Id. Because no other country would accept him and the exclusion order barred him from entering the United States, Mezei faced the prospect of indefinite detention at Ellis Island. Id. at 208-09, 73 S.Ct. 625.
Like Mezei, Borrero has not effected an entry into the United States. He is physically present in the United States only because he was paroled into the country by the INS. Parole does not constitute an entry. 8 U.S.C. §§ 1101(a)(13)(A)-(B), 1182(d)(5)(A). Borrero refers us to cases supporting the proposition that even aliens unlawfully present in the United States are guaranteed due process of law. See, e.g., Plyler v. Doe, 457 U.S. 202, 210, 102 S.Ct. 2382, 72 L.Ed.2d 786 (1982); Wong Wing v. United States, 163 U.S. 228, 238, 16 S.Ct. 977, 41 L.Ed. 140 (1896). Those cases may support extending certain constitutional protections to inadmissible aliens accused of crimes, but they do not call into question the power of the government to detain an alien who is stopped at the border. See Sierra v. INS, 258 F.3d 1213, 1218 (10th Cir.2001) (holding that an inadmissible alien is legally considered to be detained at the border and thus has no due process interest in release on parole); Hoyte-Mesa v. Ashcroft, 272 F.3d 989, 991 (7th Cir. 2001) (per curiam) (holding that Mezei remains good law after Zadvydas, thus annual parole review pursuant to the Cuban Review Plan satisfies due process); Barrera-Echavarria v. Rison, 44 F.3d 1441, 1450 (9th Cir.1995) (en banc) (“[E]xcluda-ble aliens simply enjoy no constitutional right to be paroled into the United States, even if the only alternative is prolonged detention.”).
Inadmissible aliens are of course not entirely without Fifth Amendment protection. See Wang v. Reno, 81 F.3d 808, 813 (9th Cir.1996) (that parolee was forced to give testimony that would lead to his “near certain execution” upon his return to China shocked the conscience of the court and violated his substantive due process rights). We hold, however, that the regulations governing the parole of Mariel Cubans, 8 C.F.R. § 212.12, are well within the sovereign prerogative of the executive branch to set immigration policy and do not violate the Fifth Amendment’s Due Process Clause. There is no contention that the government failed to follow these procedures here. Accordingly, the judgment is reversed, and the case is remanded to the district court with direction to dismiss the petition.