Three days before his scheduled execution for the murder of Annie Lester, James Edward Reid filed an action pursuant to 42 U.S.C.A. § 1983 (West 2003) asserting that the means by which the Commonwealth of Virginia (“the State”) intended to carry out his execution constituted cruel and unusual punishment in violation of the Eighth Amendment. The district court dismissed the action, reasoning that the complaint was properly construed as a petition for a writ of habeas corpus for which Reid, having already sought habeas relief in the federal courts, was required to obtain the permission of this court. See 28 U.S.C.A. § 2244(b)(3) (West Supp. 2004). Reid now appeals this order, and for the reasons set forth below, we reverse and remand for farther proceedings. 1

I.

Reid pleaded guilty to Lester’s murder and was sentenced to death. The Virginia Supreme Court rejected Reid’s claims on appeal, see Reid v. Commonwealth, 256 Va. 561, 506 S.E.2d 787 (1998), and his *502 petition for habeas relief. Reid thereafter filed a petition for a writ of habeas corpus in federal district court. That court denied relief, and we affirmed. See Reid v. True, 349 F.3d 788 (4th Cir.), cert. denied, - U.S. -, 124 S.Ct. 979, 157 L.Ed.2d 810 (2003).

The State scheduled Reid’s execution for December 18, 2003. On December 15, Reid filed his § 1983 claim asserting, upon information and belief, that the State intended to employ a combination of three drugs — sodium thiopental or sodium pentothal, pancuronium bromide or Pavulon, and potassium chloride — in executing him. Reid alleged that this combination of chemicals would cause him “to consciously suffer an excruciatingly painful and protracted death.” Compl. at 4. Specifically, Reid alleged that the sodium pentothal, intended to render him unconscious during the execution, would wear off or be neutralized by the Pavulon before the execution was complete, causing Reid to experience the painful effects of the potassium chloride used to bring about cardiac arrest; Reid’s agony would be masked, however, by the paralyzing effect of the Pavulon. Reid sought “a permanent injunction barring Defendants from executing Plaintiff in the manner they currently intend.” Id. at 5.

The district court dismissed, reasoning that “[a] ‘challenge to the manner of execution is a challenge seeking to interfere with the sentence itself, and thus, is properly construed as a petition for habeas corpus.’ ” Reid v. Johnson, No. 3:03cv1039, slip op. at 2 (E.D.Va. Dec. 16, 2003) (quoting In re Sapp, 118 F.3d 460, 462 (6th Cir. 1997)). Reid thereafter filed a notice of appeal and sought a stay of execution from this court. We granted Reid a stay of execution pending appeal and held this appeal in abeyance pending a decision by the United States Supreme Court in Nelson v. Campbell, — U.S. -, 124 S.Ct. 2117, 158 L.Ed.2d 924 (2004).

II.

42 U.S.C.A. § 1983 and 28 U.S.C.A. § 2254 (West 1994 & Supp. 2004) are two different means of seeking redress for unconstitutional action by state officials. See Heck v. Humphrey, 512 U.S. 477, 480, 114 S.Ct. 2364, 129 L.Ed.2d 383 (1994). Section 2254 “is the exclusive remedy for a state prisoner who challenges the fact or duration of his confinement and seeks immediate or speedier release, even though such a claim may come within the literal terms of § 1983.” Id. at 481, 114 S.Ct. 2364. An action styled as a § 1983 claim must be treated as a petition for habeas relief under § 2254 when success on the claim would necessarily imply the invalidity of the plaintiffs conviction or sentence. See Edwards v. Balisok, 520 U.S. 641, 645-46, 117 S.Ct. 1584, 137 L.Ed.2d 906 (1997).

The Supreme Court applied these principles in Nelson. Three days before his scheduled execution, Nelson filed a § 1983 action alleging that the state of Alabama intended to use a “cut-down” procedure to obtain venous access to execute him by lethal injection and claiming that use of this procedure would violate the Eighth Amendment. See Nelson, — U.S. at -, 124 S.Ct. at 2120. Nelson sought to permanently enjoin Alabama from using the cut-down procedure. See id. at 2121. The Supreme Court held that Nelson had stated a cognizable claim under § 1983 because he challenged only the use of the cut-down procedure, not lethal injection generally. See id. at 2123. The Court observed that Nelson’s challenge to the use of the cut-down procedure might constitute a challenge to the execution itself “[i]f as a legal matter the cut-down were a statutorily mandated part of the lethal injection protocol, or if as a factual matter *503 petitioner were unable or unwilling to concede acceptable alternatives for gaining venous access.” Id. at 2123-24.

In light of Nelson, we conclude that Reid has stated a cognizable claim under § 1983. Like Nelson, Reid does not assert that lethal injection generally is an unconstitutional method of execution. Rather, he asserts only that the particular protocol the State plans to use is impermissible; he acknowledges that other protocols would pass constitutional muster. See Pl.-Appellant’s Reply to Def.’s Mot. to Vacate as Moot the Order of Dec. 17, 2003 at 10-11. Additionally, it appears that the execution protocol at issue here is a matter of Department of Corrections policy, not statute or regulation. See Aff. of Anthony M. Parker at 2. Under these circumstances, Reid’s challenge to the protocol does not implicate the validity of his death sentence. See Nelson, — U.S. at---, 124 S.Ct. at 2123-24.

As did the Supreme Court in Nelson, we note that Reid’s statement of a cognizable § 1983 claim does not necessarily entitle him to relief. The question remains whether Reid should be afforded preliminary injunctive relief in order to pursue his § 1983 claim. See id. at 2125-26 (noting that “the mere fact that an inmate states a cognizable § 1983 claim does not warrant the entry of a stay as a matter of right”); Gomez v. United States Dist. Ct., 503 U.S. 653, 654, 112 S.Ct. 1652, 118 L.Ed.2d 293 (1992) (per curiam) (describing equitable considerations pertinent to an award of preliminary injunctive relief in an eleventh-hour attempt to stay execution). The propriety of a stay pending litigation of Reid’s claim is a matter best addressed by the district court in the first instance.

III.

For the reasons set forth above, we reverse and remand for further proceedings consistent with this opinion. The stay of execution will remain in effect for ten days after the issuance of our mandate or until Reid reinstates his request for preliminary injunctive relief in the district court, whichever occurs first. 2

REVERSED AND REMANDED