OPINION
Jonathan King appeals from the district court’s order dismissing his petition for a writ of habeas corpus. King filed a “mixed” habeas petition in federal court— that is, one including both exhausted and unexhausted claims — just two days before the end of the one-year statute of limitations applicable under the Anti-Terrorism
*1135
and Effective Death Penalty Act (“AED-PA”).
See
28 U.S.C. § 2244(d)(1). King then asked the district court to stay the petition and dismiss his unexhausted claims so that he could exhaust them in state court before adding them back into the stayed federal petition, thereby invoking the three-step procedure outlined by this Court in
Kelly v. Small,
The district court denied King’s request. Instead, it ordered King to either abandon his unexhausted claims and proceed with his exhausted claim or dismiss the entire action without prejudice. King did neither. The district court then dismissed King’s unexhausted claims and allowed the case to proceed only with respect to King’s one remaining fully-exhausted claim.
1
We hold that, in doing so, the district court applied an erroneous legal standard. Contrary to the district court’s order, the
Kelly
procedure remains available after the Supreme Court’s decision in
Rhines v. Weber,
I.
King is currently serving a 32-year sentence for two counts of attempted second-degree robbery, two counts of second-degree robbery, two counts of assault with a firearm, and one count of willfully evading a pursuing police officer. King unsuccessfully appealed his conviction to the California Court of Appeal and then to the California Supreme Court, which affirmed in an order that became final on May 18, 2004. On May 16, 2005, King filed a habeas petition in U.S. District Court, just two days before the end of AEDPA’s one-year limitations period. See 28 U.S.C. § 2244(d)(1).
King’s habeas petition acknowledged that nine of his ten claims were unexhausted at the time of filing. On May 18, 2005, King filed a motion appearing to invoke the three-step procedure outlined in
Kelly,
which affirmed the three-step stay and abeyance procedure first articulated in
Calderon v. U.S. Dist. Ct. (Taylor),
Later in the same motion, however, Bang expressly referenced the U.S. Supreme Court’s decision in
Rhines. Rhines
declared that “in limited circumstances,” federal district courts have the authority to stay a mixed habeas petition and hold the entire petition — exhausted and unexhausted claims alike — in abeyance while
*1136
the petitioner returns to state court to exhaust his remedies there.
In other words, King proposed two different approaches to his mixed petition: one (Kelly) which would not require good cause but also would not leave the entire mixed petition pending in district court, and a second (Rhines) which would require a good cause showing and would leave the entire mixed petition pending in district court.
On May 24, 2005, before the district court ruled on his motion, King filed a state habeas petition in Los Angeles County Superior Court, raising all nine of his unexhausted claims. After the Superior Court denied the petitions and King’s state court appeal failed, King petitioned for review to the California Supreme Court. While the state habeas proceedings were pending, the magistrate judge assigned to King’s federal habeas case issued a Report and Recommendation (R & R) in which he recommended denying King’s request for a stay and also recommended that King be ordered to either delete all nine of his unexhausted claims and proceed with his one exhausted claim or dismiss the entire petition and file a new petition after exhausting his state court remedies. The magistrate judge discussed the requirements outlined in Rhines and determined that King had not demonstrated “good cause” for failure to exhaust nine of his ten claims. The R & R contained no discussion of the alternative Kelly procedure.
King filed an objection to the magistrate judge’s R & R, arguing that he did have good cause for his failure to exhaust his state remedies. On October 7, 2005, the district court adopted the magistrate judge’s R & R. Unlike the magistrate judge, the district court recognized that King’s motion most clearly tracked the three-step stay-and-abeyance procedure outlined in
Kelly,
and it proceeded to analyze the motion under that rubric. The district court held, however, that Rhines’s good cause standard applies to the
Kelly
procedure as well, reasoning that both
Kelly
and
Rhines
are directed at solving the same problem — namely, the interplay between AEDPA’s one-year statute of limitations and the total exhaustion requirement first articulated in
Rose v. Lundy,
In addition, the court stated, “even assuming
the[.Rhines
] good cause standard does not apply to the Ninth Circuit’s three step procedure [outlined in
Kelly
], it is not at all clear that the
[Kelly]
procedure benefits petitioner.” The court provided two related reasons why that might be so: First, at the time King requested a stay, the one-year limitations period had already run, so King could not possibly exhaust his claims in state court and return to federal court in time to file his claims. Second, “the recent Supreme Court decision in
Mayle v. Felix,
[
Denying Kang’s motion to stay the petition and dismiss the unexhausted claims, the district court ordered King to file within five days either a notice of abandonment of the unexhausted claims or a request to dismiss the entire action without prejudice. The district court’s order went on to state that “[i]f no written response is received within five days of the filing date of this Order, ... the Court will dismiss the unexhausted claims and order further proceedings with respect to the one exhausted claim in the Petition.” King did not respond to the district court’s order, and on November 2, 2005, the district court dismissed the unexhausted claims and referred the matter back to the magistrate judge for adjudication of the one remaining, exhausted claim.
That same day, approximately forty minutes before the district court’s order was filed, the California Supreme Court denied King’s petition for review on the merits, at which point the nine previouslyunexhausted claims were fully exhausted. King promptly filed a motion for reconsideration with the district court, drawing the district court’s attention to the California Supreme Court’s ruling. The district court denied King’s motion for reconsideration, explaining that its decision to deny King’s motion to stay his petition was final as of October 7, 2005, and that the California Supreme Court’s ruling therefore came too late to salvage the nine originally unexhausted claims.
King next requested leave to file an amended habeas petition with the district court which included his nine newly-exhausted claims, citing neither Kelly nor Rhines, but only Federal Rule of Civil Procedure 15(a). On January 6, 2006, the district court once again refused King’s request, this time stating that the proposed amendment was improper because those nine claims had been dismissed with prejudice (although the district court had not so stated in its previous order) and also because they were now time-barred under AEDPA. Consequently, the district court proceeded to consider King’s one originally-exhausted claim, which it ultimately dismissed on the merits.
King now appeals both the district court’s refusal to implement the three-step procedure in Kelly and its denial of his motion to file a first amended complaint. This court granted a certificate of appealability on four issues: (1) whether the Kelly three-step procedure for staying a fully exhausted habeas petition remains available after Rhines; (2) if so, whether a petitioner seeking to stay a fully exhausted petition pursuant to the Kelly three-step procedure must demonstrate good cause for the failure to exhaust claims in state court, as is required for the stay of a mixed petition under Rhines; (3) whether King demonstrated good cause for his failure to exhaust nine of his ten claims in state court; and (4) whether, after dismissing the nine unexhausted claims, the district court erred in denying King leave to file a first amended petition under FRCP 15(a), where the newly-exhausted claims sought to be added were the same as those raised in the original petition. 3
*1138
We would not need to address the first and second certified issues if we determined that King had demonstrated good cause under
Rhines
for his failure to exhaust his state court remedies before filing his petition in federal court. In its October 7 order, adopting the magistrate judge’s R & R, the district court rejected King’s good cause argument both because it was based on factual allegations not presented to the magistrate judge, and because those factual allegations were hearsay and insufficiently detailed to establish good cause. Given our deferential standard of review of both the district court’s good cause finding and its refusal to consider new evidence submitted in opposition to the magistrate’s findings,
see Brown v. Roe,
We discuss the remaining issues in turn below.
II.
Habeas petitioners have long been required to adjudicate their claims in state court — that is, “exhaust” them — before seeking relief in federal court.
See, e.g., United States ex rel. Kennedy v. Tyler,
In 1982, the U.S. Supreme Court interpreted the exhaustion rule in the habeas context as requiring “total exhaustion” of “mixed” petitions — that is, those petitions that contain both exhausted and unexhausted claims.
Rose,
The 1996 passage of AEDPA, which imposes a one-year statute of limitations on the filing of habeas petitions in federal court,
see
28 U.S.C. § 2244(d)(1), greatly changed the practical impact of
Rose’s
total exhaustion principle. AEDPA’s one-year limitations period meant that petitioners whose mixed petitions were dismissed under
Rose
ran the risk of being time-barred from bringing their claims again, once exhausted, in federal court. To ad
*1139
dress this problem, this Circuit developed a three-step procedure for mixed petitions, allowing (1) a petitioner to amend his petition to delete any unexhausted claims; (2) the court in its discretion to stay and hold in abeyance the amended, fully exhausted petition, providing the petitioner the opportunity to proceed to state court to exhaust the deleted claims; and (3) once the claims have been exhausted in state court, the petitioner to return to federal court and amends his federal petition to include the newly-exhausted claims.
See Taylor,
In
Kelly,
this Court expressed concern that circumstances might arise in which the “outright dismissal [of a mixed petition would] render it unlikely or impossible for the petitioner to return to federal court within the one-year limitation period imposed by [AEDPA].”
Three years after
Kelly,
the Supreme Court, in
Rhines,
considered “whether a federal district court has discretion to stay [a] mixed petition to allow the petitioner to present his unexhausted claims to the state court in the first instance, and then return to federal court for review of his perfected petition.”
Rhines,
Shortly after
Rhines,
in
Jackson v. Roe,
III.
The case now before us picks up where Jackson left off. Kang argues that the district court erred in refusing to allow him to use the three-step procedure outlined in Kelly and Taylor. He maintains that the district court should have allowed him to dismiss his unexhausted claims, stay his fully exhausted petition, and file an amended petition containing all his claims once they had been exhausted, without requiring a showing of good cause for his failure to exhaust earlier. For the reasons explained below, we reiterate that the Kelly procedure remains available after Rhines and hold that its availability is not premised upon a showing of good cause.
As we recognized in
Jackson, “Rhines
did
not ...
comment on the validity of the three-step stay-and-abeyance procedure approved in
Taylor
and
Kelly.”
Rhines carved out an exception to Rose’s total exhaustion rule, allowing a mixed petition to remain pending in federal court under limited circumstances. When implemented, the Rhines exception eliminates entirely any limitations issue with regard to the originally unexhausted claims, as the claims remain pending in federal court throughout. It was to prevent abuse of this special dispensation, and to preserve the central purposes of the total exhaustion rule (avoiding delay and piecemeal litigation), that the Supreme Court in Rhines limited the availability of the exception to circumstances in which the petitioner had good cause for his failure to exhaust all his claims in state court before filing his federal habeas petition.
In contrast, the Kelly procedure, because it does not leave a mixed petition pending, does not sanction any exception to Rose and so does not present the same dangers of abuse. Indeed, Kelly is not only a more cumbersome procedure for petitioners, but also a riskier one. A petitioner seeking to use the Kelly procedure will be able to amend his unexhausted claims back into his federal petition once he has exhausted them only if those claims *1141 are determined to be timely. And demonstrating timeliness will often be problematic under the now-applicable legal principles.
Under
Duncan v. Walker,
Given these strictures, the
Kelly
procedure is therefore unlikely to be abused by late-filing habeas petitioners who have not exhausted all of their federal claims and for whom the expiration of AEDPA’s one-year limitations period is imminent. Nor does the
Kelly
procedure involve any exceptional judicial action. It is in part an exercise of litigants’ usual prerogative, specifically recognized in
Rose,
to amend complaints if they can do so to make them cognizable in federal court,
see Rose,
In short, nothing about the
Kelly
procedure goes sufficiently beyond normal court procedures or raises such elevated concerns about possible abuse to require the imposition of a special standard such as “good cause.” We therefore hold that district courts retain the same degree of discretion they had before
Rhines
to implement the
Kelly
procedure, particularly when “outright dismissal [of an entire mixed petition would] render it unlikely or impossible for the petitioner to return to federal court within the one-year limitation period imposed by [AEDPA].”
Kelly,
IV.
So holding .does not decide the case in King’s favor, however. As we noted in
Jackson,
and as we recognize again here, “the Supreme Court’s ... decision in
Mayle,
imposing stricter limitations than previously required by this court for amendments to relate back to the original filing date, is likely to make ... [the
Kelly
] approach less useful for petitioners in many instances.”
King challenges in only one respect the district court’s finding that his claims do not relate back under Mayle: he urges that Mayle is satisfied so long as his new claims are related to any of the claims that appeared (properly or not) in the original petition he filed with the district court. Because King’s nine new claims are the same as the nine unexhausted claims he attempted to include in his original petition, he asserts, the new claims are sufficiently related to the original filing date to be considered timely under Mayle.
We disagree. The only sensible interpretation of
Mayle
is that it requires new claims to relate back to claims properly contained in the original petition — that is, those claims that were exhausted at the time of filing. Only this interpretation of
Mayle
comports with
Duncan’s
reasoning about the goal of exhaustion in habeas cases. Wary of “creating] ... opportunities for delay and piecemeal litigation without advancing the goals of comity and federalism that the' exhaustion requirement serves,”
Rejecting such a self-defeating interpretation, we hold that
Mayle
requires a comparison of a petitioner’s new claims to the properly exhausted claims left pending in federal court, not to any earlier version of the complaint containing claims subsequently dismissed for failure to exhaust.
Cf. Rasberry v. Garcia,
*1143
Critically, King in his briefs before this court does not address the relevant
Mayle
question, making no attempt to argue that his nine previously unexhausted claims share a “common core of operative facts” with his one exhausted claim. Mayle,
Conclusion
In sum, we hold that the three-step stay-and-abeyance procedure outlined in
Kelly
remains available. Although this procedure might not be as useful for petitioners today in avoiding untimeliness as it was when
Kelly
was decided, district courts still maintain discretion to implement
Kelly’s
three-step stay-and-abeyance procedure, particularly when “outright dismissal [of a mixed petition would] render it unlikely or impossible for the petitioner to return to federal court within the one-year limitation period imposed by [AEDPA].”
Kelly,
AFFIRMED.
Notes
. King does not appeal the court’s subsequent dismissal of this claim on the merits.
.
Mayle
v.
Felix,
. Notably absent from the certificate of appealability is the question whether the district *1138 court abused its discretion in denying King's November 8 motion for reconsideration premised on the fact that all nine of King’s previously unexhausted claims had been fully exhausted by the time the district court issued its November 2 order. Because this issue was not covered in the certificate of appealability or raised in King's opening brief to this court, we do not address it. See 9th Cir. R. 22.1(e) ("Petitioners shall brief only issues certified by the district court or the court of appeals. Alternatively, if a petitioner concludes during the course of preparing the opening brief, that an uncertified issue should be discussed in the brief, the petitioner shall first brief all certified issues under the heading, 'Certified Issues,' and then, in the same brief, shall discuss any uncertified issues under the heading, 'Uncertified Issues.' ”).
. Robbins reaffirmed Kelly but rejected the requirement that district courts sua sponte consider implementing the three-step procedure.
