Reversed and remanded by published opinion. Judge KING wrote the majority opinion, in which Judge MOTZ joined. Judge DIAZ wrote a dissenting opinion.
OPINION
KING, Circuit Judge:In 2005, William Scott MacDonald was convicted after a bench trial in the Circuit Court of the City of Colonial Heights, Virginia, of two offenses: the misdemeanor offense of contributing to the delinquency of a minor, in contravention of Virginia Code section 18.2-371; and the felony offense of violating the Commonwealth’s criminal solicitation statute, found in section 18.2-29. The criminal solicitation statute provides that “[a]ny person age eighteen or older who commands, entreats, or otherwise attempts to persuade another person under age eighteen to commit [a predicate felony, i.e.,] a felony other than murder,” shall be guilty of a felony. Va. Code § 18.2-29.
*156The predicate felony for MacDonald’s criminal solicitation offense was the Commonwealth’s “Crimes Against Nature” statute, which criminalizes, inter alia, “carnal knowledge” by one person of another by the anus or mouth, an act commonly known as sodomy. Va.Code § 18.2-361(A). MacDonald was sentenced to ten years in prison (with nine years suspended) for criminal solicitation, plus twelve months on the misdemeanor offense. Upon release, MacDonald was placed on probation and compelled to register as a sex offender.
In 2009, after failing to obtain relief on direct appeal and in state postconviction proceedings, MacDonald filed a 28 U.S.C. § 2254 petition in the Eastern District of Virginia. MacDonald alleged, among other things, that his criminal solicitation conviction, insofar as it was predicated on the anti-sodomy provision of Virginia Code section 18.2-361(A), contravened the Constitution. More specifically, MacDonald contended that the predicate anti-sodomy provision had been rendered invalid by the Supreme Court’s decision in Lawrence v. Texas, 539 U.S. 558, 123 S.Ct. 2472, 156 L.Ed.2d 508 (2003) (striking down Texas anti-sodomy statute as facially violative of Fourteenth Amendment’s Due Process Clause). The district court rejected MacDonald’s constitutional challenges to section 18.2-361 (A) and dismissed his § 2254 petition. See MacDonald v. Holder, No. 1:09-cv-01047, 2011 WL 4498973 (E.D.Va. Sept. 26, 2011) (the “Opinion”).1
On October 24, 2011, MacDonald filed a timely notice of appeal. He thereafter requested the issuance of a certificate of appealability (“COA”) from this Court. See 28 U.S.C. § 2253(c)(1)(A). We granted his COA request on April 17, 2012, identifying the issue for appeal as whether Virginia Code section 18.2-361(A) is unconstitutional either facially or as applied in MacDonald’s case, in light of the Supreme Court’s Lawrence decision. The COA circumscribes this appeal to an examination of the constitutionality of a single aspect of section 18.2-361(A), which provides:
If any person ... carnally knows any male or female person by the anus or by or with the mouth, or voluntarily submits to such carnal knowledge, he or she shall be guilty of a [felony.]
We herein use the term “anti-sodomy provision” to refer to the foregoing portion of section 18.2-361(A).2 As explained below, we are constrained to vacate the district court’s judgment and remand for an award of habeas corpus relief on the ground that the anti-sodomy provision facially violates the Due Process Clause of the Fourteenth Amendment.
I.
MacDonald was forty-seven years old at the time of the events giving rise to his state court convictions.3 On the evening of September 23, 2004, MacDonald telephoned seventeen-year-old Amanda John*157son, a young woman he had met through a mutual acquaintance. MacDonald and Johnson arranged to meet that night at a Home Depot parking lot in Colonial Heights. When they arrived at the parking lot, MacDonald got into the backseat of Johnson’s vehicle and they drove to the nearby home of Johnson’s grandmother. Johnson went into her grandmother’s residence to retrieve a book, and when she returned to the vehicle MacDonald asked her to “suck his dick.” J.A. 51. MacDonald also suggested that they have sex in a shed in Johnson’s grandmother’s yard. Johnson declined both proposals, however, and she drove MacDonald back to the Home Depot parking lot.
Nearly three months later, in December 2004, MacDonald filed a report with the Colonial Heights police maintaining that Johnson had abducted and sexually assaulted him. MacDonald thereafter met ■with and was interviewed by Detective Stephanie Early. MacDonald advised Early that, sometime in September, Johnson had paged him and asked that he meet her in the Home Depot parking lot. MacDonald stated that, once they met, he got into Johnson’s car and she drove them away. When MacDonald asked Johnson where she was going, she did not respond. MacDonald told her, “[T]his has got to stop, lose my number, I’m married, don’t call me anymore.” J.A. 59. MacDonald also advised Detective Early that he and Johnson stopped at a location on Canterbury Lane in Colonial Heights, and “at that point Ms. Johnson forcibly removed his penis from his pants and performed oral sex against his will.” Id. MacDonald acknowledged that he knew Johnson was only seventeen years old.
Soon thereafter, Detective Early met with and interviewed Johnson, who gave a sharply conflicting account of what had occurred. Crediting Johnson’s version of the events, Early secured three arrest warrants for MacDonald, charging: (1) the felony criminal solicitation offense; (2) the misdemeanor offense of contributing to the delinquency of a minor; and (3) the misdemeanor offense of “knowingly giv[ing] a false report as to the commission of a crime to the Police with the intent to mislead,” in violation of Virginia Code section 18.2-461. See J.A. 4-6. MacDonald was arrested on January 25, 2005. He was prosecuted in the Juvenile and Domestic Relations Court of Colonial Heights on the false police report charge, and in the circuit court on the other two charges.
On May 25, 2005, MacDonald pleaded guilty to filing a false police report, in connection with his false complaint to Detective Early. As a result, he was sentenced to twelve months in jail, with six months suspended. On June 7, 2005, MacDonald moved in the circuit court to dismiss the criminal solicitation charge on the ground that the predicate felony — the anti-sodomy provision — -violated his due process rights. Relying on Lawrence v. Texas, MacDonald asserted that the Supreme Court had invalidated all state statutes that prohibit “consensual sodomy between individuals with the capacity to consent.” J.A. 24. A bench trial was conducted in the circuit court on July 12, 2005, where Johnson, Early, MacDonald, and MacDonald’s wife testified.4 After the trial had concluded, on July 25, 2005, the circuit court denied the motion to dismiss, ruling that the anti-sodomy provision was not being unconstitutionally applied to MacDonald. The following day, the court *158found MacDonald guilty of solicitation to commit a felony (i.e., the anti-sodomy provision), and deferred ruling on the misdemeanor offense of contributing to the delinquency of a minor. On August 2, 2005, the circuit court convicted MacDonald of the misdemeanor offense, and it sentenced him on both offenses.
II.
A.
MacDonald appealed his circuit court convictions to the Court of Appeals of Virginia. In doing so, he argued that, in light of Lawrence v. Texas, the anti-sodomy provision was facially invalid “insofar as it relates to consensual sodomy between unrelated individuals who have reached the age of consent,” by infringing on the liberty interests protected by “the Due Process Clause of the Fourteenth Amendment.” S.J.A. 14. MacDonald thus maintained that the anti-sodomy provision could not serve as a predicate felony for the criminal solicitation offense.
In January 2007, the state court of appeals ruled that MacDonald lacked “standing to assert [the facial due process claim]” and dismissed his appeal. See MacDonald v. Commonwealth, No. 1939-05-2, 2007 WL 43635 (Va.Ct.App. Jan. 9, 2007). In that regard, the court relied on its ruling in McDonald v. Commonwealth, 48 Va. App. 325, 630 S.E.2d 754 (2006).5 The previous appeal related to other criminal proceedings involving petitioner MacDonald, specifically his prior convictions on four counts of violating Virginia’s anti-sodomy provision, twice each with two young women who were sixteen and seventeen years old. There, the court of appeals had rejected MacDonald’s Fourteenth Amendment due process claims, holding that, because his offenses involved minors, his as-applied claim failed and he thus lacked standing to pursue a facial challenge. See McDonald, 630 S.E.2d at 756 (citing Ulster Cnty. v. Allen, 442 U.S. 140, 154-55, 99 S.Ct. 2213, 60 L.Ed.2d 777 (1979) (“As a general rule, if there is no constitutional defect in the application of the statute to a litigant, he does not have standing to argue that it would be unconstitutional if applied to third parties in hypothetical situations.”)).6 In the present case, on September 7, 2007, the Supreme Court of Virginia summarily denied MacDonald’s pro se petition for appeal, and then, on November 9, 2007, denied his petition for rehearing.7
*159B.
On September 16, 2009, MacDonald, again proceeding pro se, filed his 28 U.S.C. § 2254 petition in the Eastern District of Virginia. Therein, MacDonald theorized that his conviction was “in violation of the ex post facto guarantee of the U.S. Constitution because [the anti-sodomy provision] is Facially Unconstitutional and also because it carries punishments that are in direct conflict with Equal Protection of the Law.” J.A. 292. MacDonald maintained, as he had at each previous opportunity, that the Lawrence decision invalidated all state anti-sodomy provisions, and that the Supreme Court “acted in accordance with numerous prior precedents that struck down laws impinging upon the liberty guarantees of the Fifth and Fourteenth Amendments.” Id. at 301. The district court, “[i]n deference to petitioner’s pro se status,” trifurcated MacDonald’s constitutional challenges into (1) an ex post facto claim; (2) a facial due process attack; and (3) an as-applied due process challenge to the anti-sodomy provision. See Opinion 5.8
In its Opinion, the district court dismissed MacDonald’s ex post facto claim “to the extent that [it] differs from the facial attack,” as proeedurally barred under the rule of Slayton v. Parrigan, 215 Va. 27, 205 S.E.2d 680, 682 (1974). See Opinion 6; see also supra note 6. Proceeding to MacDonald’s facial due process challenge, the district court employed the deferential § 2254(d) standard of review to withhold relief. See infra Part III. The court concluded that the Virginia Court of Appeals had reasonably applied Ulster County to decide that MacDonald lacked standing to pursue such a claim because his conduct was not constitutionally protected. See Opinion 8. Finally, determining that the anti-sodomy provision was constitutional as applied to MacDonald, the district court endorsed the state court’s rationale that, because the Commonwealth had properly treated seventeen-year-olds as children, and because the Lawrence decision had stressed that “[t]he present case does not involve minors,” 539 U.S. at 578, 123 S.Ct. 2472, the anti-sodomy provision could constitutionally serve as a predicate offense under the solicitation statute. See Opinion 8-9. The district court further explained,
The Court of Appeals of Virginia’s determination is based on clearly established federal law. Virginia considers persons aged sixteen and seventeen to be children, and the Supreme Court in Lawrence explicitly stated that the ruling did not apply to sexual acts involving children. Thus, the holding that Va. Code § 18.2-361 is not unconstitutional as applied to MacDonald is not contrary to, or an unreasonable] application of, federal law.
Id. at 9 (citations omitted).
III.
The Antiterrorism and Effective Death Penalty Act of 1996 (“AEDPA”) governs a federal court’s handling of a 28 U.S.C. § 2254 petition filed by a state prisoner. We review de novo a district court’s denial of a § 2254 petition. See Deyton v. Keller, 682 F.3d 340, 343 (4th Cir.2012). Pursuant to AEDPA, however, when a habeas petitioner’s constitutional *160claim has been “adjudicated on the merits in State court proceedings,” we may not grant relief unless the state court’s adjudication “resulted in a decision that was contrary to, or involved an unreasonable application of, clearly established Federal law, as determined by the Supreme Court of the United States,” or “resulted in a decision that was based on an unreasonable determination of the facts in light of the evidence presented in the State court proceeding.” 28 U.S.C. § 2254(d).
rv.
A.
In this appeal, MacDonald pursues both facial and as-applied due process challenges to the anti-sodomy provision. He contends not only that the anti-sodomy provision was unconstitutional as applied to him, but also that Lawrence v. Texas compels the facial invalidation of the anti-sodomy provision under the Fourteenth Amendment.9 Even though, as the Supreme Court of Virginia emphasized, Lawrence did not involve minors, MacDonald argues that “[t]he Lawrence Court did not preserve those applications of Texas’s [sodomy] law to the extent that it would apply to ‘minors’ or in any other circumstance. It invalidated the law in toto.” Br. of Appellant 10. MacDonald maintains that he possesses standing to pursue his facial challenge under the Due Process Clause because the anti-sodomy provision was rendered unconstitutional by Lawrence. He relies on established Supreme Court authority for the proposition that standing exists
“where the statute in question has already been declared unconstitutional in the vast majority of its intended applications, and it can fairly be said that it was not intended to stand as valid, on the basis of fortuitous circumstances, only in a fraction of cases it was originally designed to cover.”
Br. of Appellant 14 (quoting United States v. Raines, 362 U.S. 17, 23, 80 S.Ct. 519, 4 L.Ed.2d 524 (1960)).
MacDonald next asserts that the Virginia courts have impermissibly interpreted Lawrence as authorizing them to recast the anti-sodomy provision — -which by its terms bans all sodomy offenses — and apply the provision solely to sodomy offenses that involve minors. In explaining his position, MacDonald contends that
[t]he courts’ re-writing of the [anti-sodomy provision] wrongly “substitute^] the judicial for the legislative department of the government” and creates a “dangerous” precedent to encourage legislatures to “ ‘set a net large enough to catch all possible offenders, and leave it to the courts to step inside’ to announce to whom the statute may be applied.”
Br. of Appellant at 17-18 (quoting Ayotte v. Planned Parenthood of N. New Eng., 546 U.S. 320, 330, 126 S.Ct. 961, 163 L.Ed.2d 812 (2006)). MacDonald further argues that the Virginia courts’ rewriting of the anti-sodomy provision was contrary to the intent of Virginia’s General Assembly, because the judicially rewritten statute is at odds with other Virginia criminal statutes regulating the sexual conduct of persons over eighteen with younger persons. Cf. Va.Code § 18.2-63 (prohibiting carnal knowledge of a child between thirteen and fifteen); Va.Code § 18.2-370 (prohibiting persons over eighteen from *161certain “indecent” acts with children under fifteen, including soliciting sodomy).
More particularly, Virginia Code section 18.2~370(A) prohibits any person over eighteen from proposing certain sexual conduct (including sodomy) to “any child under the age of 15 years.” The foregoing provision, MacDonald maintains, was plainly not intended to criminalize activity with minors fifteen or older. He thus contends that Virginia’s judicial rewriting of the anti-sodomy provision, rendering it applicable to the solicitation of sodomy from a minor under eighteen, runs afoul of the age specification (“any child under the age of 15 years”) embedded in section 18.2-370(A). MacDonald further asserts that the judicial redrafting of the anti-sodomy provision by the Virginia courts contravened his due process rights because he did not have — and could not have had — fair notice that the anti-sodomy provision would be construed in a way that renders it applicable to his conduct.
The Commonwealth responds to MacDonald’s contentions by maintaining that Lawrence did not “establish the unconstitutionality of solicitation statutes generally ..., or MacDonald’s solicitation in particular.” Br. of Appellee 8. Positing that Lawrence simply does not apply to statutes that criminalize sodomy involving a minor, Virginia emphasizes the district court’s determination that the anti-sodomy provision is constitutional as applied to MacDonald. The Commonwealth then asserts that MacDonald lacks standing to pursue a facial challenge to the anti-sodomy provision under the Supreme Court’s Ulster County decision, because the provision can be constitutionally applied in various circumstances, including those underlying this appeal.10
B.
1.
Put succinctly, the Ulster County decision does not operate to deny standing for MacDonald to pursue a facial due process challenge to the anti-sodomy provision. Under the Article III case-or-controversy requirement, a litigant must assert a concrete interest of his own. See Lujan v. Defenders of Wildlife, 504 U.S. 555, 560-61, 112 S.Ct. 2130, 119 L.Ed.2d 351 (1992) (explaining that Article III requires (1) that the plaintiff has suffered an “invasion of a legally -protected interest,” (2) that there is a causal connection between the injury “fairly traceable” to *162the challenged action; and (3) that it is likely that the injury will be “redressed by a favorable decision” (citations omitted)). The Virginia courts ruled that MacDonald had not asserted his own concrete interest in his facial challenge, but rather was pursuing the interests of third parties, in that the anti-sodomy provision is constitutional as applied to him. Under that theory, MacDonald could only pursue a facial challenge to the anti-sodomy provision as it applies to others. This determination of the jurisdictional predicate for standing to sue relied entirely on an unfavorable legal resolution of the merits of MacDonald’s as-applied constitutional claim. In turn, our resolution of MacDonald’s as-applied claim informs — at least under the theories propounded by the state and district courts — whether MacDonald possesses standing to assert a facial challenge to the anti-sodomy provision.
In Ulster County, the Supreme Court assessed a habeas petition filed by three state prisoners, challenging a New York statute that permitted a jury to presume that two firearms found in the vehicle in which they were riding had been jointly possessed by them all. The Second Circuit declared the statute facially unconstitutional, emphasizing its broad reach in potentially applying the presumption to vehicle occupants “ Vho may not know they are riding with a gun’ ” or “ ‘who may be aware of the presence of the gun but not permitted access to it.’ ” 442 U.S. at 146, 99 S.Ct. 2213 (quoting Allen v. Cnty. Court, Ulster Cnty., 568 F.2d 998, 1007 (2d Cir.1977)).
The Supreme Court reversed the court of appeals, however, ruling that the Second Circuit had unnecessarily addressed the issue of the statute’s facial invalidity. According to the Court, the presumption was constitutionally applied to the three Ulster County petitioners, in that the firearms had been discovered in a handbag belonging to the vehicle’s fourth occupant — a sixteen-year-old female. The Court explained the applicable principle as this:
A party has standing to challenge the constitutionality of a statute only insofar as it has an adverse impact on his own rights. As a general rule, if there is no constitutional defect in the application of the statute to a litigant, he does not have standing to argue that it would be unconstitutional if applied to third parties in hypothetical situations.
Ulster Cnty., 442 U.S. at 154-55, 99 S.Ct. 2213. The Court’s ruling on standing to pursue a facial challenge, as in this case, depended on an unfavorable threshold resolution of an as-applied challenge. If the statute had been unconstitutionally applied to the petitioners in Ulster County, their own rights would have been adversely affected, and, therefore, reaching the merits of their facial challenge may have been appropriate.
Because, as we explain below, the anti-sodomy provision is unconstitutional when applied to any person, the state court of appeals and the district court were incorrect in deeming the anti-sodomy provision to be constitutional as applied to MacDonald. MacDonald is thus asserting his own concrete injury, and the state court’s standing determination, as endorsed by the district court, was contrary to and involved an unreasonable application of clearly established federal law, as determined by the Supreme Court of the United States.11
*1632.
In Lawrence, the Supreme Court plainly held that statutes criminalizing private acts of consensual sodomy between adults are inconsistent with the protections of liberty assured by the Due Process Clause of the Fourteenth Amendment. 539 U.S. at 578, 123 S.Ct. 2472. The statute declared invalid in Lawrence provided that “[a] person commits an offense if he engages in deviate sexual intercourse with another individual of the same sex.” Id. at 563, 123 S.Ct. 2472. The conduct for which the Lawrence defendants were prosecuted qualified as “deviate sexual intercourse,” in that it amounted to “contact between any part of the genitals of one person and the mouth or anus of another person,” that is, sodomy. Id. The Supreme Court granted certiorari on three issues: (1) whether the criminalization of strictly homosexual sodomy violated the Equal Protection Clause of the Fourteenth Amendment; (2) more broadly, whether criminalization of sodomy per se between consenting adults contravened the fundamental liberty and privacy interests protected by the Fourteenth Amendment’s Due Process Clause; and (3) whether Bowers v. Hardwick, 478 U.S. 186, 106 S.Ct. 2841, 92 L.Ed.2d 140 (1986), which upheld against facial challenge a Georgia statute criminalizing all sodomy, should be overruled.
On the third question, relating to Bowers v. Hardwick, the Court readily con-eluded that “[t]he rationale of Bowers does not withstand careful analysis.... Bowers was not correct when it was decided, and it is not correct today.... Bowers v. Hardwick should be and now is overruled.” Lawrence, 539 U.S. at 577-78, 123 S.Ct. 2472.12 Though acknowledging the equal protection argument as “tenable,” the Court premised its constitutional holding on the Due Process Clause of the Fourteenth Amendment, surmising that if it were to invalidate the statute “under the Equal Protection Clause[,] some might question whether a prohibition would be valid if drawn differently, say, to prohibit the conduct both between same-sex and different-sex participants.” Id. at 574-75, 123 S.Ct. 2472 (emphasis added). The Court underscored that, although the conduct proscribed by the Texas statute might be sincerely condemned by many as immoral, “[t]hese considerations do not answer the question before us____The issue is whether the majority may use the power of the State to enforce these views on the whole society through operation of the criminal law.” Id. at 571, 123 S.Ct. 2472. The Lawrence Court thus recognized that the facial due process challenge in Bowers was wrongly decided. Because the invalid Georgia statute in Bowers is materially indistinguishable from the anti-sodomy provision being challenged here, the latter provision likewise does not survive the Lawrence decision.13
*164The Commonwealth’s efforts to diminish the pertinence of Lawrence in connection with MacDonald’s challenge to the anti-sodomy provision — an enactment in no way dissimilar to the Texas and Georgia statutes deemed unconstitutional by the Supreme Court — runs counter to Martin v. Ziherl, 269 Va. 35, 607 S.E.2d 367 (2005). In that case, the Supreme Court of Virginia evaluated the constitutionality of a state statute having nothing to do with sodomy, but instead outlawing ordinary sexual intercourse between unmarried persons. The state supreme court nonetheless acknowledged that Lawrence was sufficiently applicable to require the statute’s invalidation.
The Martin decision reversed the trial court’s judgment against the plaintiff, who sought damages because the defendant had infected her with herpes. The defendant had demurred to Martin’s motion for judgment, pointing out that Virginia law barred tort recovery for injuries sustained while participating in an illegal activity. In its ruling, the state supreme court concluded that there was “no relevant distinetion between the circumstances in Lawrence ” and those in Martin, recognizing that, “but for the nature of the sexual act, the provisions of [the challenged statute] are identical to those of the Texas statute which Lawrence determined to be unconstitutional.” Martin, 607 S.E.2d at 370 & n*.14 The anti-sodomy provision, of course, prohibits the same sexual act targeted by the Texas statute that failed constitutional muster in Lawrence.
Although both parties in the Martin case were adults, there is no valid reason why the logic of that ruling should not have applied with equal force to the ruling of the Court of Appeals of Virginia in MacDonald’s case. It is not sufficient that the Martin plaintiff was doubtlessly more deserving of the court’s sympathy than MacDonald. True enough, the Supreme Court implied in Lawrence that a state could, consistently with the Constitution, criminalize sodomy between an adult and a minor. See Lawrence, 539 U.S. at 572, 123 S.Ct. 2472 (documenting “emerging awareness that liberty gives substantial protee*165tion to adult persons in deciding how to conduct their private lives in matters pertaining to sex” (emphasis added)); id. at 573, 123 S.Ct. 2472 (pointing out that, in thirteen states where sodomy was yet proscribed, “there is a pattern of nonenforcement with respect to consenting adults acting in private” (emphasis added)); id. at 578, 123 S.Ct. 2472 (“The present case does not involve minors. It does not involve persons who might be injured or coerced or who are situated in relationships where consent might not easily be refused. It does not involve public conduct or prostitution.” (emphasis added)). The Court’s ruminations concerning the circumstances under which a state might permissibly outlaw sodomy, however, no doubt contemplated deliberate action by the people’s representatives, rather than by the judiciary.
Recently, we had occasion to consider a facial challenge to a much different statute, but the analysis in that case informs the issue presented here. See United States v. Moore, 666 F.3d 313 (4th Cir.2012). Moore, who had been convicted under 18 U.S.C. § 922(g) for being a felon in possession of a firearm, asserted a facial challenge to § 922(g) under the Second Amendment and the Supreme Court’s decision in District of Columbia v. Heller, 554 U.S. 570, 128 S.Ct. 2783, 171 L.Ed.2d 637 (2008).15 We explained that, “[ujnder the well recognized standard for assessing a facial challenge to the constitutionality of a statute, the Supreme Court has long declared that a statute cannot be held unconstitutional if it has constitutional application.” Moore, 666 F.3d at 318 (citations omitted). Moore contended that the Supreme Court’s decision in Heller, which struck down the District of Columbia’s general prohibition on the possession of handguns, rendered § 922(g)’s firearm restriction violative of the Second Amendment. The Heller Court took care to observe however, that certain prohibitions on handgun possession, such as the possession of firearms by felons, are “presumptively lawful.” 554 U.S. at 627 & n. 26, 128 S.Ct. 2783. Seizing upon that language, we readily rejected Moore’s Second Amendment facial challenge to § 922(g).
The Latorence Court, as in Heller, struck down a specific statute as unconstitutional while reserving judgment on more carefully crafted enactments yet to be challenged. The salient difference between § 922(g) and the anti-sodomy provision, however, is that § 922(g), in a relatively narrow fashion, regulates the possession of firearms by felons, while the anti-sodomy provision, like the statute in Lawrence, applies without limits. Thus, although the Virginia General Assembly might be entitled to enact a statute specifically outlawing sodomy between an adult and an older minor, it has not seen fit to do so.16 The anti-sodomy provision does not mention the word “minor,” nor does it remotely suggest that the regulation of sexual relations between adults and children had anything to do with its enactment. In these circumstances, a judicial reformation of the anti-sodomy provision to criminalize MacDonald’s conduct in this ease, and to do so in harmony with Law*166rence, requires a drastic action that runs afoul of the Supreme Court’s decision in Ayotte v. Planned Parenthood of Northern New England, 546 U.S. 320, 126 S.Ct. 961, 163 L.Ed.2d 812 (2006).
In Ayotte, the Court recognized the important principle that, “[gjenerally speaking, when confronting a constitutional flaw in a statute, we try to limit the solution to the problem. We prefer, for example, to enjoin only the unconstitutional applications of a statute while leaving other applications in force, or to sever its problematic portions while leaving the remainder intact.” 546 U.S. at 328-29, 126 S.Ct. 961. The Court also acknowledged, however, the dangers of too much meddling:
[Mjindful that our constitutional mandate and institutional competence are limited, we restrain ourselves from rewriting state law to conform it to constitutional requirements even as we strive to salvage it.... [Mjaking distinctions in a murky constitutional context, or where line-drawing is inherently complex, may call for a far more serious invasion of the legislative domain then we ought to undertake.... All the while, we are wary of legislatures who would rely on our intervention, for it would certainly be dangerous if the legislature could set a net large enough to catch all possible offenders, and leave it to the courts to step inside to announce to whom the statute may be applied. This would, to some extent, substitute the judicial for
the legislative department of the government.
Id. at 329-30, 126 S.Ct. 961 (citations, alterations, and internal quotation marks omitted); see also Reno v. Am. Civil Liberties Union, 521 U.S. 844, 884-85, 117 S.Ct. 2329, 138 L.Ed.2d 874 (1997) (explaining, in upholding facial constitutional challenge, that “[tjhis Court ‘will not rewrite ... law to conform it to constitutional requirements’ ” (quoting Virginia v. Am. Booksellers Ass’n, Inc., 484 U.S. 383, 397, 108 S.Ct. 636, 98 L.Ed.2d 782 (1988))); United States v. Nat’l Treasury Emp. Union, 513 U.S. 454, 479, 115 S.Ct. 1003, 130 L.Ed.2d 964 (1995) (recognizing “[ojur obligation to avoid judicial legislation”); Aptheker v. Sec’y of State, 378 U.S. 500, 515, 84 S.Ct. 1659, 12 L.Ed.2d 992 (1964) (warning against judicial rewriting of statute to “save it against constitutional attack”).
It is accurate for us to observe that facial constitutional challenges to state statutes are generally disfavored, see Wash. State Grange v. Wash. State Republican Party, 552 U.S. 442, 450-51, 128 S.Ct. 1184, 170 L.Ed.2d 151 (2008), and the general rule when a defect appears is “partial, rather than facial, invalidation,” see Ayotte, 546 U.S. at 329, 126 S.Ct. 961. We are confident, however, that we adhere to the Supreme Court’s holding in Lawrence by concluding that the anti-sodomy provision, prohibiting sodomy between two persons without any qualification, is facially unconstitutional.17
*167A consequence of the Ayotte decision could be that a statute closely related to the anti-sodomy provision — for example, Virginia Code section 18.2-361(B), which criminalizes incestuous sodomy - involving both minors and adults — might well survive review under Lawrence, as may that part of section 18.2-361(A) that outlaws bestiality. See supra note 2. The anti-sodomy provision itself, however, which served as the basis for MacDonald’s criminal solicitation conviction, cannot be squared with Lawrence without the sort of judicial intervention that the Supreme Court condemned in Ayotte.
V.
Pursuant to the foregoing, we reverse the judgment of the district court and remand for an award of habeas corpus relief.
REVERSED AND REMANDED.
. The district court’s unpublished Opinion is found at J.A. 400-12. (Citations herein to "J.A. _” refer to the contents of the Joint Appendix filed by the parties in this appeal. Citations to "S.J.A__” refer to the contents of the Supplemental Joint Appendix.)
. The remainder of Virginia Code section 18.2-361(A) prohibits bestiality by criminalizing the carnal knowledge “in any manner [of] any brute animal." The constitutionality of the bestiality portion of subsection (A) is not challenged in this proceeding nor affected by today’s decision.
.Our account of the facts is largely derived from the evidence presented at MacDonald’s bench trial in state court. The facts are recited in the light most favorable to the Commonwealth, as the prevailing party in the trial. See Roach v. Angelone, 176 F.3d 210, 219 (4th Cir.1999).
. At his bench trial, MacDonald testified con-sistendy with his initial version of the events of September 23, 2004, under which he had been abducted and sexually assaulted by Johnson. By its verdict, the trial court rejected that testimony.
. Though the appellant’s last name in the earlier appeal is spelled differently, it is clear that both appeals involved the same individual, known here as petitioner William Scott MacDonald.
. After the state court of appeals affirmed his earlier sodomy convictions, MacDonald sought review in the Supreme Court of Virginia. See McDonald v. Commonwealth, 274 Va. 249, 645 S.E.2d 918 (2007). MacDonald's efforts were to no avail, however, as the state supreme court rejected MacDonald’s as-applied challenge. The court reasoned that the anti-sodomy provision was constitutional as applied because MacDonald's victims were minors, and it concluded that his facial claim had not been preserved in the trial court. See id. at 921, 924. Thereafter, MacDonald pursued his due process contentions in federal habeas proceedings, but the district court dismissed his 28 U.S.C. § 2254 petition. See MacDonald v. Johnson, No. 1:08-cv-00781, 2009 WL 3254444 (E.D.Va. Oct. 9, 2009). Our Court declined to issue a COA on June 24, 2010. See MacDonald v. Johnson, 384 Fed.Appx. 273 (4th Cir.2010).
.MacDonald subsequently sought state post-conviction relief, raising claims of ineffective assistance of counsel and violations of his ex post facto guaranties. The state supreme court dismissed MacDonald’s petition for appeal, however, ruling, inter alia, that his ex post facto claim was "barred because this non-jurisdictional issue could have been raised at trial and on direct appeal and, thus, is not cognizable in a petition for a writ of *159habeas corpus.” MacDonald v. Dir. of the Dep't of Con., No. 348987, slip op. at 4 (Va. Oct. 21, 2008) (citing Slayton v. Parrigan, 215 Va. 27, 205 S.E.2d 680, 682 (1974)).
. The Opinion does not specify that MacDonald's as-applied challenge was based on the Due Process Clause of the Fourteenth Amendment. The district court recognized, however, that MacDonald relied on the Lawrence decision for his pursuit of this claim, and Lawrence was decided on Fourteenth Amendment due process grounds.
. MacDonald also seeks to invalidate his criminal solicitation conviction on equal protection and ex post facto grounds. Inasmuch as we conclude that MacDonald is entitled to relief on his primary due process claim, we need not consider the alternative bases he has asserted.
. The Commonwealth also contends that the resolution of MacDonald's earlier case relating to his 2005 sodomy convictions — particularly our 2010 denial of a COA, see supra note 6 — has become the law of the case, or, alternatively, is collaterally estopped from relitigation. We disagree. First, the doctrine of law of the case restricts a court to legal decisions it has made on the same issues in the same case. See Christianson v. Colt Indus. Operating Corp., 486 U.S. 800, 815-16, 108 S.Ct. 2166, 100 L.Ed.2d 811 (1988). As the Commonwealth admits, this case is not the same as MacDonald’s earlier case, and thus, the law of the case doctrine does not apply. Second, collateral estoppel, which might preclude relitigation of an issue, is an affirmative defense that the Commonwealth waived by not first raising it in the district court. See Fed.R.Civ.P. 8(c). Finally, even if collateral estoppel was not waived, that doctrine requires that the issue be "actually determined and necessarily decided in prior litigation in which the party against whom collateral es-toppel is asserted had a full and fair opportunity to litigate.” Va. Hosp. Ass’n v. Baliles, 830 F.2d 1308, 1311 (4th Cir.1987). Our denial of a COA in the earlier case — in which MacDonald was proceeding pro se — is not precedent here, does not constitute a decision on the merits of MacDonald's constitutional claims, and did not afford MacDonald a full and fair opportunity to litigate. See Miller-El v. Cockrell, 537 U.S. 322, 331, 123 S.Ct. 1029, 154 L.Ed.2d 931 (2003) (recognizing that "a COA ruling is not the occasion for a ruling on the merit of petitioner's claim”).
. In our resolution of the standing issue, we are, of course, necessarily concluding that the Virginia courts wrongly decided MacDonald's as-applied challenge to the anti-sodomy provision. As explained below, however, we see the provision as not only unconstitutional as *163applied to MacDonald, but as facially invalid in light of Lawrence v. Texas, and we resolve the case on those grounds alone. See Richard H. Fallon, Jr., As-Applied Challenges and Third-Party Standing, 113 Harv. L. Rev. 1321, 1336-39 (2000) (recognizing that a statute's application will "sometimes unmistakably, even necessarily, yield the conclusion that a statute is invalid, not merely as applied to the facts, but more generally or even in whole”).
. The Georgia statute upheld in Bowers, and deemed unconstitutional by the Supreme Court in Lawrence, was strikingly similar to the anti-sodomy provision. It provided, in pertinent part, as follows:
"A person commits the offense of sodomy when he performs or submits to any sexual act involving the sex organs of one person and the mouth or anus of another....”
Bowers, 478 U.S. at 188 n. 1, 106 S.Ct. 2841 (quoting Ga.Code § 16-6-2(a) (1984)).
. Our good colleague in dissent accords controlling weight to a single instance of word choice in Lawrence, seizing upon Justice Ken*164nedy’s observation that the "case” then before the Court did not involve minors, rather than noting that the underlying "statute” failed to target minors specifically. See post at 168. Justice Kennedy could have accurately used both words interchangeably, as could have Justice White in Bowers, had he also chosen to write concerning what the dispute — or litigation, or matter, or issue, or case, or statute — was not about. The anti-sodomy provision in this case, being indistinguishable for all practical purposes from the statute that we now know should have been negated in Bowers, also does not involve minors. That is precisely why, in conformance with Ayotte, the provision cannot be saved through superhuman efforts. See infra at 165-66.
The dissent’s finely honed distinction that, unlike Lawrence and Bowers, this "case” involves minors, is made possible solely by the Commonwealth’s decision to institute prosecution of a man who loathsomely solicited an underage female to commit an act that is not, at the moment, a crime in Virginia. The Commonwealth may as well have charged MacDonald for telephoning Ms. Johnson on the night in question, or for persuading her to meet him at the Home Depot parking lot. The legal arm of the Commonwealth cannot simply wave a magic wand and decree by fiat conduct as criminal, in usurpation of the powers properly reserved to the elected representatives of the people.
. It is worth noting that the Martin court rejected as waived the defendant's argument that the plaintiff lacked standing to contest the statute's constitutionality (in that she was unlikely to be prosecuted), but nonetheless assured itself that its ruling did not amount to an advisory opinion, inasmuch as "the Court's decision on the constitutionality of [the challenged statute] will determine Martin's right to pursue her tort claim for damages.” 607 S.E.2d at 369.
. Section 922(g) provides, in pertinent part, that "[i]t shall be unlawful for any person ... who has been convicted in any court of[] a crime punishable for a term exceeding one year ... to possess ... any firearm or ammunition."
. As explained heretofore, it is a felony in Virginia for an adult to solicit sodomy from "any child under the age of 15 years.” Va. Code § 18.2-370(A). Because Johnson was seventeen years old when she was solicited by MacDonald, he could not be charged with violating that statute.
. The matter before us evidences a rather plain example of state action that is flatly contrary to controlling Supreme Court precedent, and therefore cannot stand. The restraints of AEDPA do not preclude federal intervention in these relatively infrequent instances where the petitioner's right to relief is manifest. See Elmore v. Ozmint, 661 F.3d 783, 872 (4th Cir.2011) (rejecting suggestion that “our job is solely to rubber-stamp the state ... court," notwithstanding state's “flouting of clear Supreme Court precedent,” and envisioning "meaningful role for the federal courts in safeguarding the constitutional rights of state prisoners”). And though we have nothing but the utmost respect for the point of view expressed by our dissenting friend as to the proper sweep of Lawrence, the dissent's reliance for support on characterizations made in passing by our sister circuits, see post at 170, is unavailing. Those decisions did not address the salient issue in this *167appeal, and thus lack the demonstrated contemplation and logical force necessary to muddle what the Supreme Court clearly established in Lawrence.