OPINION
McKEE, Circuit Judge.Brian Tyson, a state prisoner, appeals the district court’s dismissal without prejudice of the habeas petition he filed pursuant to 28 U.S.C. § 2254. The district court concluded that it had no jurisdiction because it was an unauthorized second or successive petition. For the reasons that follow, we disagree and we will therefore reverse and remand for further proceedings.
I.
Because we write primarily for the parties, we will recite only so much of the facts and procedural history of this case as are necessary for the disposition of this appeal. While intricate procedural histories are not infrequent in federal review of state convictions, the procedural labyrinth formed by this petitioner’s attempt to get federal habeas review is as intricate and involved as any we have seen.
On September 17, 1997, at approximately 9:30 p.m., Tyson fatally shot Damon Millner in the chest. A state jury thereafter convicted Tyson of third-degree murder and possessing an instrument of a crime, and he was sentenced to thirty years imprisonment for the murder conviction and a concurrent term of one to two years for possessing an instrument of a crime.
A. Direct Appeal in State Court.
Tyson appealed his convictions to the Pennsylvania Superior Court on February 20, 2001. After several years in which Tyson filed repeated petitions and other motions, the Superior Court affirmed his convictions by an unpublished opinion dat*745ed January 24, 2004. Commonwealth v. Tyson, 847 A.2d 762 (Pa.Super.2004) (Table) (No. 691 EDA 2001)(en banc). In that opinion, the Superior Court held that Tyson’s eleven claims of ineffective assistance of trial counsel were prematurely raised pursuant to Commonwealth v. Grant, 572 Pa. 48, 813 A.2d 726 (2002).1 On November 16, 2004, the Pennsylvania Supreme Court denied Tyson’s petition for allowance of appeal.
B. First Federal Habeas Petition.
While his direct appeal in state court was proceeding, Tyson filed a pro se § 2254 petition for habeas relief in the district court on April 24, 2002. Tyson v. Greenspan, Dist. Ct. No. 02-2413. The petition was assigned to a Magistrate Judge who, on January 14, 2003, issued a Report and Recommendation (“R & R”) concluding that the petition should be denied and dismissed without prejudice for failure to exhaust state remedies. On February 10, 2003, the District Court approved the R & R and dismissed the petition without prejudice. Tyson attempted to appeal that dismissal, but we denied a certificate of appealability (“COA”) on November 18, 2003. Tyson v. Greenspan, No. 03-1689 (3d Cir. Nov. 18, 2003).
On October 3, 2002, Tyson filed a “Petition for a Writ of Mandamus,” which the District Court treated as a § 2254 habeas petition by order entered November 15, 2002, and subsequently dismissed. Tyson appealed that decision, but we dismissed for lack of jurisdiction. No. 02-4545. He subsequently filed motions for relief under Fed.R.Civ.P. 60(b) and other nunc pro tune motions for relief, but the district court dismissed the case on July 16, 2004 and denied mine pro tunc relief on October 12, 2004.
C. Second and Third Federal Habeas Petitions.
On March 18, 2004, Tyson filed his second § 2254 petition. Tyson v. Officer Myers, Dist. Ct. No. 04-1173. On June 21, 2004, he filed a third § 2254 petition, claiming that he did not receive notice that his second petition (No. 04-1173) was docketed. Tyson v. Officer Myers, Dist. Ct. No. 04-2723. Tyson began to litigate both petitions and, as the Magistrate Judge noted, Tyson admitted in one of his many court filings that his petition docketed at No. 04-2723 raised the same Ex Post Facto and Due Process challenges he raised in his petition docketed at No. 04-1173.
On March 15, 2005, the Magistrate Judge issued another R & R concluding that Tyson’s habeas petition docketed at No. 04-1173 should be dismissed without prejudice for failure to exhaust state remedies. In doing so, the Magistrate Judge specifically warned Tyson that he must file his state Post Conviction Relief Act petition no later than February 13, 2006, to avoid procedural default of his claims on federal habeas review.
On that same day, the Magistrate Judge issued a R & R in response to the habeas petition docketed at No. 04-2723. The judge noted that because the claims raised in that petition are essentially the same as the claims raised in Tyson’s habeas petition docketed at No. 04-1173, he recommended that the petition docketed at No. 04-2723 should be dismissed with prejudice as an unauthorized second or successive petition.
On April 25, 2005, the District Court adopted the Reports and Recommendations for both petitions. Tyson subsequently filed numerous motions to alter or amend the judgment or correct the record *746under Rule 60(b) as to the petition docketed at No. 04-1178, which the District Court denied by orders dated April 27, 2005, May 10, 2005, and May 24, 2006.
Tyson also filed' numerous appeals in connection with the petition docketed in the District Court at No. 04-1173. On December 28, 2004, we dismissed his appeal (No. 04-2602) from the order concerning the proper form for his petition and filing fees for lack of jurisdiction. By order dated January 21, 2005, we denied his petition for a writ of mandamus (No. 04-4181). On August 16, 2005, we denied his requests for COAs on the merits. We concluded that the District Court had properly determined that Tyson had failed to exhaust his state remedies (No. 05-2353). On September 19, 2005, we dismissed his petition for reargument (No. 05-2601). By order dated August 22, 2005, we denied Tyson’s petition for a writ of mandamus (No. 05-3529). By order dated October 17, 2005, we denied his request for a COA regarding the district court’s denial of his request for a stay (No. 05-3671).
All the while, Tyson sought to re-open his second habeas petition in the District Court by filing another Rule 60(b) motion on May 18, 2006. The District Court denied that motion on May 24, 2006.2
D. State Post-Conviction Actions.
During this time, Tyson filed a pro se petition for relief under the Pennsylvania Post Conviction Relief Act (“PCRA”), 42 Pa.C.S. § 9541 et seq., in state court on June 30, 2005. Counsel was appointed on January 9, 2006, but the PCRA court granted Tyson permission to proceed pro se on April 10, 2006. The PCRA court dismissed his petition on June 5, 2006, after sending Tyson notice of its intention to dismiss the petition without a hearing pursuant to Pa.R.Crim.P. 907.
Tyson appealed to the Pennsylvania Superior Court contending that the PCRA court erred by (1) “not recusing [herself], failing to state the reasons in the pre-dismissal notice, and failing to notify [him] of his pro se status;” (2) “ignoring] federal law by determining that the retroactive application of Grant did not violate the Ex Post Facto[J Due Process, Contracts Taking, [and] Bill of Attainder Clauses, and [his] right to counsel, of choice and a speedy appeal;” (3) determining that he was “not completely and constructively deprived of counsel and did not suffer abandonment of loyalty-conflict of interest at trial and on appeal, that it never erred during [his] trial, that [he] did not raise the original 11 pre-Grant claims, and that [he] is not actually and legally innocent;” and (4) rejecting unidentified claims of “newly-after-discovered evidence.” SA 143. In the body of his brief, Tyson raised numerous other claims
The Superior Court affirmed the PCRA court’s dismissal on May 1, 2007. Commonwealth v. Tyson, 929 A.2d 248 (Pa.Super.2007) (Table). The Superior Court held that Tyson had waived the more than thirty-two claims raised in the body of his brief because he did not include them in his statement of questions involved in violation of Pa.R.App.P. 2116(a). The court also denied the claims that were actually before it either because they were waived, or because they lacked merit. First, it found that Tyson’s allegation of trial court bias was waived because it was not raised on direct appeal, but that it would fail in any event as completely unsubstantiated. Second, it noted that Tyson failed to state a claim for PCRA relief in contending that the state courts erred in applying Com*747monwealth v. Grant, supra,, and that any claim of a constitutional violation was waived for lack of support and elaboration. Third, it held there was no merit to Tyson’s claim of ineffectiveness of trial and appellate counsel. Fourth, it found that Tyson waived his claim of after-discovered evidence because of his failure to provide any intelligible discussion to support it. On July 5, 2007, the Superior Court denied Tyson’s petition for reargument. Tyson then filed a petition for allowance of appeal with the Pennsylvania Supreme Court, which was denied on October 26, 2007.3 On November 8, 2007, Tyson filed an “Application for Reconsideration,” which the Pennsylvania Supreme Court denied on April 3, 2008.
E. The Habeas Petition That Is The Subject Of This Appeal.
The foregoing serpentine background brings us to the petition that is now pending before us. On January 23, 2006, Tyson filed another habeas petition (Dist.Ct. No. 06-0290), which is the subject of this appeal. In an order entered January 30, 2006, the district court granted Tyson leave to proceed in forma pauperis, ordered him to complete the standard form for filing petitions pursuant to § 2254, and directed him to return the completed form to the Clerk of Court within thirty days. Tyson returned the completed form on February 7, 2006. In his petition Tyson alleged that: (1) he had suffered an “Ex Post Facto — Due Process — contracts— choice of counsel — Takings—Bill of Attainder Clause violation” on the ground that “after [his] direct appeal was financed, briefed, and argued in reliance on the preexisting [Commonwealth v. Hubbard, 472 Pa. 259, 372 A.2d 687 (1977) ] rule system [prior to Commonwealth v. Grant, supra,] the Supreme Court (via the Superior Court) imposed new duties, impaired the obligation of [his] attorney-client contract, and changed the legal consequences of previously completed appeal acts,” Pet. 1112(A); (2) the state courts “refused to give ‘just compensation’ for destroying [his] vested legal and financial reliance in the pre-existing rule [prior to Grant ] and allow [him] to adapt to the rule change,” Pet. ¶ 12(B); and (3) he suffered a “speedy appeal — Due Process violation” on the ground that the state courts “prolonged [his] appeal for nearly two years and then constructively denied it on the basis of the Ex Post Facto Grant rule,” Pet. ¶ 12(C).
The District Court did not order the Commonwealth to file a response to the petition. Instead, it dismissed the petition without prejudice on February 13, 2006. It wrote:
On January 23, 2006, [Tyson] filed the above-captioned petition in this court seeking Habeas Corpus relief pursuant to 28 U.S.C. § 2254. [Tyson] has filed a previous petition in this court pursuant to 28 U.S.C. § 2254. labeled 04-cv-2723, which attacked the same conviction and/or sentence and was considered, and denied, on the merits. The Antiterrorism and Effective Death Penalty Act of 1996, 28 U.S.C. § 2241-2266, provides in relevant part that before such a second or successive petition is filed in the district court, the prisoner must first get permission to file in the district court from the circuit court pursuant to 28 U.S.C. § 2244(b)(3)(A), and that without such circuit permission, the district court lacks subject matter jurisdiction to consider such a habeas petition. Stewart v. Martinez-Villareal, 523 U.S. 637, 118 S.Ct. 1618, 140 L.Ed.2d 849 (1998); Felker v. Turpin, 518 U.S. 651, 116 S.Ct. *7482333, 135 L.Ed.2d 827 (1996); Benchoff v. Colleran, 404 F.3d 812 (3d Cir.2005).
App. 1. Accordingly, the District Court dismissed the petition without prejudice “on the grounds that [it] lacks subject matter jurisdiction over it.” Id.
On March 9, 2006, Tyson filed a notice of appeal, and we granted Tyson’s application for the COA filed on April 13, 2006. Our COA reads:
The foregoing request for a certificate of appealability is granted with regard to [Tyson’s] contention that the District Court improperly dismissed his § 2254 petition as an unauthorized second or successive petition. See Villanueva v. United Stales, 346 F.3d 55, 60 ([2d Cir.] 2003); Christy v. Horn, 115 F.3d 201, 208 (3d Cir.1997). The parties should also address whether [Tyson] has exhausted state court remedies.
F. Subsequent Filings.
Not surprisingly, our grant of a COA did not end Tyson’s filings in the District Court. On March 17, 2007, Tyson filed an additional habeas petition, also docketed at No. 06-0290, alleging various acts of malfeasance on the part of the state courts and the Commonwealth of Pennsylvania. Tyson requested, among other things, that the District Court waive the exhaustion requirement or grant his request for federal habeas relief. He attached to the petition a newly completed standard federal habeas petition form in which he asserted variations of the claims he previously asserted, in addition to new claims, viz., (1) that the state courts violated [the] “Ex Post Facto, Due Process, Contracts, Takings, Bill of Attainder clauses and right to counsel of choice and a speedy trial,” Pet. ¶ 12(A); “complete and constructive denial of counsel at trial for entirely failing to object to prosecutorial misconduct, judicial misconduct and error, abandonment of loyalty,” together with allegedly newly discovered, yet unspecified, evidence of his actual innocence, Pet. ¶ 12(b), and (3) constructive denial of counsel and conflict of interest on appeal” based on counsel’s “fail[ure] to challenge the after-the-fact rule change,” filing of “frivolous briefs in [Tyson’s] name, and failfure] to offer any argument why [the] appeal should be heard” or raise “meritorious claims,” Pet. ¶ 12(C). A short time later, on March 31, 2007, Tyson filed a “Motion for Recusal.” In an order entered March 31, 2007, the District Court held that this new federal habeas petition, together with the motion for recu-sal, would be held in abeyance pending the outcome of this appeal.
On April 5, 2007, Tyson filed yet another federal habeas petition, again under No. 06-0290, captioned “Application for Relief for Writ of Habeas Corpus re: Actual and Legal Innocence.” In an order entered April 9, 2007, the District Court held that this petition would also be held in abeyance pending the outcome of this appeal.
On August 1, 2007, Tyson filed an “Application for Release Pending, Appeal,” which the District Court denied in an order entered August 13, 2007. On August 28, 2007, Tyson filed a “Motion for Order Directing Release Pending Appeal under F.R.A.P. 23(b),” which the district court denied in an order entered on September 11, 2007.
In the meantime, Tyson filed another federal habeas petition, again under No. 06-0290, on September 6, 2007, followed by another copy of the petition on September 7, 2007, this time with two affidavits attached. In an order entered September 14, 2007, the District Court ruled that consideration of these petitions would be held in abeyance pending the outcome of this appeal.
On September 27, 2007, Tyson filed a notice of appeal from the District Court’s September 11, 2007 order denying his request for release pending appeal. That *749appeal was docketed independently of this appeal. Tyson v. Beard, No. 07-3884. By order dated December 11, 2007, we rejected Tyson’s claim that he was entitled to release and closed the appeal.
II.
The District Court’s holding that it lacked jurisdiction to consider Tyson’s ha-beas petition is incorrect. AEDPA’s provision requiring a petitioner to seek permission, see 28 U.S.C. § 2244(b)(3)(A), by a court of appeals before filing a “second or successive” habeas petition necessarily only applies where the petitioner’s initial filing can be considered a “first” habeas petition. A petition is considered a “prior application” for purposes of 28 U.S.C. § 2244(b) only if it was adjudicated on the merits. See Villanueva v. United States, 346 F.3d 55, 60 (3d Cir.2003). In contrast to the language of the district court’s order, Tyson’s third petition was not considered or rejected on the merits. See Tyson v. Meyers, Dist. Ct. No. 04-2723. Nor do Tyson’s first or second petitions, which were dismissed for failure to exhaust, form the basis for requiring permission under § 2244. See Christy v. Horn, 115 F.3d 201, 208 (3d Cir.1997) (if the initial petition was dismissed for failure to exhaust, § 2244 does not apply). Accordingly, Tyson has not yet filed a “first” petition for purposes of § 2244. Therefore, the District Court erred by dismissing Tyson’s petition which is the subject of this appeal as “second or successive.”
In our COA, we also directed that the parties address whether Tyson has exhausted his state remedies. At the time the briefs were filed, Tyson had not exhausted his state rémedies. However, as noted earlier, on April 3, 2008, the Pennsylvania Supreme Court denied Tyson’s motion for reconsideration of its denial of a petition for allowance of an appeal from the Superior Court’s affirmance of the PCRA court’s denial of his PCRA petition. Therefore, he has now exhausted his state remedies.
Inasmuch as the District Court erred in dismissing the habeas petition which is the subject of this appeal as a second or successive petition, and since he has now exhausted his state remedies, we will remand to the District Court so that court can determine which of his federal habeas petitions, all bearing No. 06-0290, contain the final and complete statement of his claims for habeas relief. Once Tyson decides which claims he wishes to pursue on federal habeas, the District Court can then review each of the claims, determine which have been properly presented to the state courts,4 and adjudicate any properly presented claims.
III.
For the above reasons, we will reverse the district court order dismissing without prejudice Tyson’s habeas petition and remand for further proceedings consistent with this opinion.5
. In Grant, the Pennsylvania Supreme Court created a general rule that ineffectiveness of counsel claims should be raised in Post Conviction Relief Act proceedings.
. Between July 2002 and January 2006, Tyson filed six other actions in the district court that were not federal habeas petitions. They included prisoner civil rights actions filed pursuant to 42 U.S.C. § 1983 and an action against his former counsel.
. Tyson also filed numerous other actions in the Pennsylvania Superior Court and the Pennsylvania Supreme Court which have nothing to do with the issue present in this appeal.
. The Commonwealth claims that certain of his claims have already been procedurally defaulted. However, we believe that a determination of that issue is best left for the district court’s determination in the first instance.
. We realize that our remand further complicates a case that, but for its relatively short time in federal court, could rival Dickens' Bleak House for its apparent potential to outlive every judge who ever has or ever will touch it (including this one). Yet, given the state of this record, we have no alternative but to require the District Court to look at this yet again.