The Anti-terrorism and Effective Death Penalty Act (“AEDPA”) provides, with some important exceptions, that state prisoners must file a federal petition for habe-as corpus within one year of the date their convictions become final. See 28 U.S.C. § 2244(d)(1). Jon Mills is an Arkansas inmate serving a life sentence for rape and first degree sexual abuse. He appeals the district court’s dismissal of his federal ha-beas petition as time-barred. The appeal requires us to determine the proper interplay between Arkansas appellate law and procedure and the provisions of AEDPA. We conclude that the one-year limitations period was tolled while Mills attempted to appeal from the denial of state postconviction relief, even though he ultimately failed to perfect the appeal. Therefore, we reverse.

Following his conviction, Mills filed a pro se petition for postconviction relief under Rule 37 of the Arkansas Rules of Criminal Procedure. The Arkansas trial court denied the petition on August 15, 1996. Four days later, Mills timely filed a notice of appeal to the Supreme Court of Arkansas. Rule 5(a) of the Arkansas Civil Rules of Appellate Procedure (which applies to criminal appeals as well) provides that the record on appeal “shall be filed with the clerk of the Arkansas Supreme Court and docketed therein within 90 days from the filing of the first notice of appeal, unless the time is extended by order of the trial court.” Mills never filed that record. There was' no court order dismissing the appeal.

Mills filed this pro se petition for federal habeas relief on October 9, 1997. Because his judgment of conviction became final prior to AEDPA’s enactment, the one-year limitations period began on April 24, 1996. See Nichols v. Bowersox, 172 F.3d 1068, 1073 (8th Cir.1999) (en banc). Thus, unless that period was tolled, Mills’s § 2254 petition is time-barred. In computing AEDPA’s one-year limitations period, the statute provides that “[t]he time during which a properly filed application for State postconviction or other collateral review ... is pending shall not be counted.” 28 U.S.C. § 2244(d)(2). Mills’s Rule 37 petition was pending on April 24, 1996, when his one-year period began, so the period of limitation was tolled — in the words of § 2244(d)(2), the time “shall not be counted”- — for as long as that petition was “pending.” The state trial court denied Mills postconviction relief on August 15, 1996. If the period of tolling ended that day, Mills’s § 2254 petition is still time-barred. The issue before us concerns the effect of the notice of appeal to the Supreme Court of Arkansas that Mills filed on August 19, 1996. In the district court’s view, “there was no appeal” because Mills took no further action after filing his notice of appeal; therefore, the court concluded, “the Rule 37 petition was pending until August 15, 1996, when the trial court denied the petition.” We granted a certificate of appealability to consider this issue. ^[1]

The tolling period under § 2244(d)(2) includes time spent on an unsuccessful appeal of the denial of state postconviction relief. See Barnett v. Lemaster, 167 F.3d 1321 (10th Cir.1999). ^[2][*883] Mills argues his failure to file the record did not affect the validity of his appeal for tolling purposes; therefore, the one-year limitation period was tolled until November 17, 1996, the end of the ninety days he was allowed under Civil Appellate Rule 5(a) to perfect the appeal by filing the record on appeal with the Supreme Court of Arkansas. The State argues that Mills’s appeal was not “pending” because he failed to timely file the record on appeal as required by Arkansas Civil Appellate Rule 5(a). ^[3]

The State’s contention finds some support in the Arkansas Supreme Court’s description of the appeal in Mitchell v. City of Mountain View, 304 Ark. 585, 803 S.W.2d 556, 557 (1991), where the record was never filed in the Supreme Court, and the appellee filed a motion to dismiss the appeal:

This [motion] procedure is unusual in that no appeal is pending in this court and were [appellants] to attempt to perfect an appeal the record would be refused by the Clerk as untimely. However, since the trial court has no power to dismiss an appeal ... if the time for appeal has expired and the prevailing party prefers to formalize that fact ... such party may file with the Clerk a partial record and move for a dismissal.

Although the Court in Mitchell referred to the appeal as not “pending” on its docket, the Court’s willingness to rule on the motion to dismiss suggests that a valid appeal was in fact commenced. That inference is confirmed by Rule 2(e) of the Arkansas Criminal Rules of Appellate Procedure, which provides in relevant part:

Failure of the appellant to take any further steps to secure the review of the appealed conviction shall not affect the validity of the appeal but shall be ground only for such action as the Supreme Court deems appropriate, which may include dismissal of the appeal. The Supreme Court may act upon and decide a case in which ... the transcript of the trial record was not filed in the time prescribed, when a good reason for the omission is shown by affidavit. However, no motion for belated appeal shall be entertained by the Supreme Court unless application has been made to the Supreme Court within eighteen (18) months of the date of ... entry of the order denying postconviction relief from which the appeal is taken.

Consistent with the plain language of Criminal Appellate Rule 2(e), the Supreme Court of Arkansas enabled potentially abandoned appeals to proceed by granting motions for leave to file untimely records in Sanders v. State, 329 Ark. 363, 952 S.W.2d 133 (1997), and in Slaughter v. State, 338 Ark. 285, 992 S.W.2d 802 (1999). See generally Novak v. J.B. Hunt Transport, 48 Ark.App. 165, 892 S.W.2d 526 (1995) (en banc).

The issue before us does not turn on whether Mills’s appeal was “pending” under Arkansas law, but instead on whether it was “pending” for purposes of 28 U.S.C. § 2244(d)(2). This is an issue of federal law. There is a long-standing federal policy that habeas petitioners must exhaust their state court remedies. See O’Sullivan v. Boerckel, — U.S. —, —-—, 119 S.Ct. 1728, 1731-32, 144 L.Ed.2d 1, —-— (1999). Congress recodified and broadly stated the exhaustion requirement in AEDPA, providing that a habeas petitioner “shall not be deemed to have exhausted the remedies available in the courts of the State ... if he has the right under the law of the State to raise, by any available procedure, the[*884] question presented.” 28 U.S.C. § 2254(c). The tolling period in § 2244(d)(2) complements that policy by extending the time for filing federal petitions while state remedies are being exhausted. Therefore, harmonizing the exhaustion requirement in § 2254(c) and the limitations tolling provision in § 2244(d)(2) is sound as a matter of statutory construction. It also furthers principles of comity by giving state appellate courts full opportunity to review state prisoners’ federal constitutional claims, and it lightens the dockets of federal courts by avoiding the need for state prisoners to file protective federal petitions before uncertain state appellate procedures have been exhausted. See Nino v. Galaza, 1999 WL 451783, at *4 (9th Cir. July 6, 1999).

In this case, if Mills had filed his federal petition during the ninety days following the filing of his notice to appeal to the Supreme Court of Arkansas, the federal petition would surely have been dismissed for failure to exhaust state remedies, because there was still time to perfect his state appeal by filing the record with the Clerk of the Arkansas Supreme Court. That being so, we conclude the state post-conviction appeal was “pending” for purposes of § 2244(d)(2) until at least November 17, 1996, the end of that ninety-day period. ^[4] Thus, Mills timely filed his federal habeas petition on October 9, 1997.

The judgment of the district court is reversed, and the case is remanded for further proceedings not inconsistent with this opinion. The parties have not addressed, and we do not consider what effect, if any, Mills’s failure to pursue his state court appeal has on the merits of his claims for federal habeas relief. See O’Rourke v. Endell, 153 F.3d 560, 566 (8th Cir.1998), cert. denied, — U.S. —, 119 S.Ct. 1048, 143 L.Ed.2d 54 (1999). That is an issue for the district court on remand.