OPINION
PER CURIAM.Marion Brown, Jr., appeals pro se from the District Court’s order dismissing his complaint. For the following reasons, we will vacate and remand for further proceedings. See 3d Cir. LAR 27.4 (2008); 3d Cir. I.O.P. 10.6.
I.
Brown was arrested at his home in Philadelphia for a parole violation on June 15, 2007. Thereafter, he was taken to one prison, transferred to another, and then ultimately incarcerated at SCI-Albion in Erie County. Brown alleges that he was due to be released on parole on May 5, 2008. Six days before his release, however, his institutional parole agent told him that a detainer had been lodged against him based on a Philadelphia County arrest warrant issued on July 7, 2007, on charges *145unrelated to his parole violation. Brown continued to be detained on the basis of the Philadelphia County arrest warrant beyond his release date. Brown alleges that someone in the institutional records office told him that Philadelphia police would execute the warrant and transfer him to Philadelphia “in the near future,” but that Philadelphia police never executed the warrant and he continued to be detained. He alleges that he contacted numerous offices regarding his situation but was unable to obtain any resolution.
Brown finally filed suit in September 2008, alleging that the Philadelphia County warrant was issued without probable cause and that his continued detention pursuant to that still-unexecuted warrant was illegal. He captioned his complaint as one under 42 U.S.C. § 1988, and sought by way of relief an “order that the warrant be lifted and plaintiff released from prison,” as well as monetary damages. He named two groups of defendants: the City of Philadelphia, its Police Commissioner and two of its detectives (the “Philadelphia defendants”), whom he holds responsible for issuing but failing to execute the arrest warrant, and the warden of SCI-Albion along with various SCI-Albion employees (the “Commonwealth defendants”), whom he holds responsible for his continued detention.
The Philadelphia defendants filed a motion to dismiss the complaint under Rule 12(b)(6), arguing that Brown’s claims against them are barred by Heck v. Humphrey, 512 U.S. 477, 114 S.Ct. 2364, 129 L.Ed.2d 383 (1994), because Brown had not yet successfully challenged the validity of his underlying conviction. The Commonwealth defendants, by contrast, filed a motion for an extension of time to answer the complaint or file an appropriate motion, explaining that “[e]xamining the relevant record” would require additional time. On January 13, 2009, the District Court granted their motion and extended their time to answer or move to dismiss until February 13. On January 23, however, before the Commonwealth defendants filed a response, the District Court entered an order granting the Philadelphia defendants’ motion to dismiss on the basis of Heck and dismissing Brown’s complaint in its entirety with prejudice. The order also denied a motion for leave to file an amended complaint that Brown had filed three days earlier. Brown appeals.1
II.
We conclude that the District Court erred in dismissing Brown’s complaint in four respects. First, the District Court should not have dismissed Brown’s § 1983 claim on the basis of Heck with prejudice. Under Heck, a plaintiff cannot recover damages if his or her claim necessarily would imply the invalidity of a conviction or sentence that has not already been invalidated. See Heck, 512 U.S. at 486-87, 114 S.Ct. 2364. That is because a § 1983 claim based on an allegedly unconstitutional conviction or sentence does not accrue until the invalidation of that conviction or sentence. See id. at 484-85, 114 S.Ct. 2364; Wallace v. Koto, 549 U.S. 384, 391, 393, 127 S.Ct. 1091, 166 L.Ed.2d 973 (2007).2 For that reason, “[w]hen a § 1983 *146claim is dismissed under Heck, the dismissal should be without prejudice.” See Fottler v. United States, 73 F.3d 1064, 1065-66 (10th Cir.1996). Thus, the District Court should not have dismissed Brown’s complaint under Heck -with prejudice.
Second, the District Court also should not have dismissed that complaint without leave to amend. Brown attached to his proposed amended complaint motions that he filed seeking relief from various Pennsylvania courts. He also attached an order issued by the Pennsylvania Court of Common Pleas for Erie County requiring the Department of Corrections to transfer him to the Philadelphia Police Department for execution of the warrant by December 8, 2008, unless it had an independent basis for his detention, failing which “any detainer lodged as a result of the charge underlying the warrant at issue is vacated effective that date.” (Dist. Ct. Docket No. 8, Ex. 18.) In his motion for leave to proceed in forma pauperis in this Court, Brown asserts that the charges underlying the arrest warrant in fact were vacated by that order. Moreover, the Department of Corrections sent a letter regarding Brown’s filing fee to the District Court on May 19, 2009 (after Brown filed this appeal), in which it stated that Brown has been released from prison. Accordingly, Heck may well raise no bar to Brown’s suit now, if it ever did. The District Court did not discuss the Court of Common Pleas’ order and did not explain why it denied Brown’s motion for leave to amend. We see no reason why that motion should not have been granted.
Third, the District Court erred in dismissing Brown’s complaint in the posture that it did. Only the Philadelphia defendants had filed a motion to dismiss. The Commonwealth defendants, by contrast, sought an extension to answer or move to dismiss, which the District Court granted. Before the Commonwealth defendants filed any response, however, the District Court dismissed Brown’s complaint in its entirety. As to those defendants, then, the District Court’s dismissal was sua sponte. Sua sponte dismissals under Rule 12(b)(6) are permissible under some circumstances but not others. In Oatess v. Sobolevitch, 914 F.2d 428 (3d Cir.1990), for example, we held that district courts may not sua sponte dismiss complaints under Rule 12(b)(6) before service of process. As we explained, in “acting without the opposing party’s input, the district court bypasses our tradition of adversary proceedings,” and “may be perceived as having abandoned the role of neutral arbiter” and instead “may appear to be conducting a private litigation with the plaintiff while the defendant sits on the sidelines.” Id. at 431. We believe the same concerns are present here. The Commonwealth defendants sought additional time to respond to the complaint, in part because they had to “examin[e] the relevant record,” and it is conceivable that they might have chosen to answer Brown’s complaint instead of moving to dismiss it. Under the circumstances, the District Court should have awaited their response.
Finally, the District Court erred in failing to address Brown’s express request for an order directing his release from *147prison. Brown began the prayer for relief in his initial complaint as follows: “I want the Court to order that the warrant be lifted and plaintiff released from prison.” He also requested monetary damages. In its order dismissing the complaint, however, the District Court wrote only that Brown “seeks monetary damages in excess of $250,000.”3 The District Court acknowledged (in discussing the Heck bar to damages) that Brown “appears to be challenging the validity and execution of detainment,” that such claims “are properly addressed through petitions for a writ of habeas corpus,” and that Brown “may elect to file a writ [sic] of habeas corpus under the appropriate statute.” As we have repeatedly explained, however, pro se filings must be liberally construed and, where a pro se complaint requests habeas relief, a district court generally should construe the complaint as a habeas petition. See Royce v. Hahn, 151 F.3d 116, 118 (3d Cir.1998).4 Where, as here, a complaint seeks both monetary damages under § 1983 and habeas relief, district courts should, when appropriate, “stay the damage action until the habeas claim has been exhausted.” Tedford v. Hepting, 990 F.2d 745, 749 (3d Cir.1993).
In this case, the District Court did not acknowledge Brown’s request for release from confinement and did not explain why it did not construe at least that aspect of his complaint as a habeas petition. The documents attached to Brown’s proposed amended complaint reveal that he sought relief from his confinement on the basis of an unexecuted arrest warrant from many Philadelphia and Commonwealth employees (and from at least three different Pennsylvania courts), some of whom may have given him incorrect and conflicting information. Although we of course find no facts here and express no opinion on the merits of Brown’s claims, those documents might be read to suggest the possibility that Brown somehow “fell through the cracks” within the Department of Corrections. Under the circumstances, the District Court should not simply have dismissed his complaint and forced him to incur “the wasted time and expense” of filing a separate action before addressing his express request for habeas relief. United States v. Miller, 197 F.3d 644, 648 (3d Cir.1999).5
Accordingly, we will vacate the District Court’s order and remand. On remand, the District Court is directed to allow Brown to file an amended complaint, and thereafter to conduct further proceedings consistent with this opinion.
. We have jurisdiction under 28 U.S.C. § 1291 and review the District Court’s dismissal under Rule 12(b)(6) de novo. See Phillips v. County of Allegheny, 515 F.3d 224, 230 (3d Cir.2008). We review for abuse of discretion the District Court’s denial of leave to amend, which generally is proper only where amendment would be inequitable or futile. See Toll Bros., Inc. v. Township of Readington, 555 F.3d 131, 137, 144 n. 10 (3d Cir.2009).
. The District Court, unlike the Philadelphia defendants, recognized that Brown's challenge was based on his continued detention pursuant to an unexecuted arrest warrant, not to his underlying conviction or parole viola-*146lion. Because Brown alleges that his detention is pursuant to a warrant, his claim likely is in the nature of a claim for malicious prosecution (rather than false arrest or false imprisonment), which must await the termination of proceedings in his favor. See Wallace. 549 U.S. at 389-90. 127 S.Ct. 1091: Heck, 512 U.S. at 484, 114 S.Ct. 2364. See also Antonelli v. Foster, 104 F.3d 899, 900-01 (7th Cir.1997) (stating same and holding that Heck applies, even in the absence of a conviction, to a claim implying invalidity of detention pursuant to an arrest warrant).
. Brown did not repeat his request for release from prison in his proposed amended complaint, but, because the District Court denied him leave to file that complaint, the complaint before it was his first.
. Before recharacterizing a state prisoner’s filing as a habeas petition, district courts generally must seek the prisoner's consent and advise him or her of the consequences of proceeding with such a petition. See Mason v. Myers, 208 F.3d 414, 417-18 (3d Cir.2000).
.Brown's request for habeas relief may be moot in light of the Department of Corrections' representation in its May 19, 2009 letter to the District Court that Brown has been released from prison. We leave it to the District Court to address that issue if and when appropriate on remand.