ORDER

DAVID M. EBEL, Circuit Judge.

Petitioner Todd Deal, a pro se petitioner who is incarcerated at Ellsworth Correctional Facility in Kansas on a 1999 Kansas conviction for first-degree murder, recently sought to appeal a decision by the U.S. District Court for the District of Kansas denying his petition for federal habeas relief under 28 U.S.C. §§ 2254. However, after he filed his request for a certificate of appealability ("COA") with this Court, a Kansas court allowed Mr. Deal to reopen one of his state court appeals. This development requires us to REVERSE the district court's decision denying Mr. Deal's habeas petition, and to REMAND the matter to the court below for consideration of whether to dismiss or stay Mr. Deal's petition while Mr. Deal exhausts his state remedies.

28 U.S.C. §§ 2244(d) sets a one-year deadline for prisoners in state custody to file habeas petitions pursuant to §§ 2254. However, this deadline is tolled for "[t]he time during which a properly filed application for State post-conviction or other collateral review with respect to the pertinent judgment or claim is pending." 28 U.S.C. §§ 2244(d)(2). The district court observed that Mr. Deal's first-degree murder conviction became final on October 9, 2001, at which point the one-year statute of limitations began to run. The limitations period was tolled when Mr. Deal filed a petition for state post-conviction relief under Kan. Stat. Ann. §§ 60-1507 on August 29, 2002, but the clock restarted when the Kansas Supreme Court denied the petition on September 20, 2005. The federal district court found that the deadline for Mr. Deal to have filed his 28 U.S.C. §§ 2254 petition was October 31, 2005. Mr. Deal, however, did not file the petition until February 14, 2006. The district court concluded that Mr. Deal's federal habeas petition was untimely.

However, sometime in 2002 or 2003, Mr. Deal also filed a motion under Kan. Stat. Ann. §§ 22-3504 to correct an "illegal sentence." Kansas courts denied the §§ 22-3504 motion. Mr. Deal filed a timely notice of appeal from the §§ 22-3504 denial in December 2003, but he did not docket the appeal within the 21-day period required by Kansas rules. See Kan. Sup.Ct. R. 2.04. According to Mr. Deal, the counsel appointed to handle his §§ 22-3504 appeal filed the notice of appeal and then with-drew from the case. Mr. Deal states that it took three to four months for a Kansas court to appoint new counsel and for that person to accept the appointment. By that time, the 21-day deadline for docketing his appeal of the denial of the §§ 22-3504 motion had passed. Mr. Deal further alleges that the newly-appointed counsel assured him the §§ 22-3504 motion was being appealed, when in reality counsel failed to pursue this appeal. Mr. Deal contends he did not learn that the illegal sentence motion was never appealed until after the federal habeas deadline had passed.

The district court concluded that although equitable tolling is available when a petitioner's failure to timely file a habeas petition is "caused by extraordinary circumstances beyond his control," Marsh v. Soares, 223 F.3d 1217, 1220 (10th Cir. 2000), Mr. Deal did not demonstrate "diligence" in pursuing his petition alleging an illegal sentence under Kan. Stat. Ann. §§ 22-3504. In considering Mr. Deal's request for COA, we determined that the exercise of diligence should not necessarily encompass a requirement of second-guessing the assurances of appointed counsel. On May 31, 2007, we granted COA on the issue of whether the time to file his petition under 28 U.S.C. §§ 2254 should be equitably tolled.

Since then, we have learned from Respondents that on April 30, 2007, Mr. Deal filed a motion with the Kansas Supreme Court to allow him to docket out of time his appeal from the denial of his §§ 22-3504 illegal sentence motion. Mr. Deal argued that his appointed counsel misled him into believing that his §§ 22-3504 appeal was pending before state courts. The Kansas Supreme Court granted his motion to docket out of time on May 30, 2007. Respondents inform us that Mr. Deal's §§ 22-3504 appeal now is pending in state court, and that the appeal relates back to the original filing date of the §§ 22-3504 motion.

Respondents, therefore, concede that Mr. Deal "has a pending post-conviction motion in state courts sufficient to toll the federal statute of limitations under 28 U.S.C. §§ 2244(d)(2)," and that "the statute of limitations period in which [Mr. Deal] may file an application for federal habeas corpus relief has not expired." See also Barnett v. Lemaster, 167 F.3d 1321, 1323 (10th Cir. 1999) (holding that "pending" under §§ 2244(d)(2) must "encompass all of the time during which a state prisoner is attempting, through proper use of state court procedures, to exhaust state court remedies with regard to a particular post-conviction application.").

Accordingly, although the district court understandably found that there were no pending actions at the time it denied Mr. Deal's habeas petition, we now must REVERSE that decision and allow Kansas state courts to decide the merits of Mr. Deal's §§ 22-3504 appeal. See Rhines v. Weber, 544 U.S. 269, 273, 125 S.Ct. 1528, 161 L.Ed.2d 440 (2005) ("interests of comity and federalism dictate that state courts must have the first opportunity to decide a petitioner's claims" (citation omitted)). We REMAND Mr. Deal's federal habeas petition to the district court for consideration of whether a stay or dismissal without prejudice would be appropriate, since Mr. Deal's petition may contain both exhausted and unexhausted claims. See Rhines, 544 U.S. at 277-78, 125 S.Ct. 1528. We believe the district court both has the discretion to make this determination, id., and is in the best position to do so, see, e.g., Akins v. Kenney, 410 F.3d 451, 456 (8th Cir. 2005); Jackson v. Roe, 425 F.3d 654, 662 (9th Cir. 2005).