j

Dwayne, Donna, and Viola Michel own property in the state of Washington. Their land shares common borders with, and in some locations is completely circumscribed by, a national wildlife refuge owned by the United States. Historically, the Michels have used roads and trails across the refuge to conduct their cattle and farming business. Since 1960, the Michels and the government have engaged in a series of disputes and negotiations over the scope of the Michels’ right of access to roads and trails across refuge land. Although the parties appeared to resolve the problem on several occasions, the dispute was always renewed. In 1992, the Michels filed suit against the United States under the Quiet Title Act seeking to quiet title to access routes across the refuge. The district court dismissed on the ground that the Michels’ claim was barred by the Act’s twelve-year statute of limitations. The Michels appeal.

II.

The Quiet Title Act waives sovereign immunity to suits against the United States “to adjudicate title disputes involving real property in which the United States claims an interest.” Block v. North Dakota, 461 U.S. 273, 275-76 , 103 S.Ct. 1811, 1814 , 75 L.Ed.2d 840 (1983). Claims under this Act must be brought within twelve years of “the date the plaintiff or his predecessor in interest knew or should have known of the claim of the United States.” 28 U.S.C. § 2409a(g).

The government argues the Michels’ action is barred because they have known since the early 1940’s that the government claimed title to the land. However, the Michels’ knowledge of the government’s claim of title was not itself sufficient to trigger the running of the limitations period on their claim of a right to use roads and trails across the refuge. To start the limitations period, *132 the government’s claim must be adverse to the claim asserted by the Michels. See Fadem v. United States, 52 F.3d 202, 207 (9th Cir.1995) (citing Knapp v. United States, 636 F.2d 279, 283 (10th Cir.1980)). If a claimant asserts fee title to disputed property, notice of a government claim that creates even a cloud on that title may be sufficient to trigger the limitations period. See California v. Yuba Goldfields, 752 F.2d 393, 394-97 (9th Cir.1985). But when the plaintiff claims a non-possessory interest such as an easement, knowledge of a government claim of ownership may be entirely consistent with a plaintiffs claim. A plaintiffs cause of action for an easement across government land only accrues when the government, “adversely to the interests of plaintiffs, denie[s] or limit[s] the use of the roadway for access to plaintiffs’ property.” Werner v. United States, 9 F.3d 1514, 1516 (11th Cir.1993) (finding that limitations period on plaintiffs’ claim of an easement over government land had not run even though plaintiffs knew of the government’s title for more than twelve years). 1

A contrary holding would lead to premature, and often unnecessary, suits. If a government claim to title were sufficient to trigger the running of the limitations period on any claim affecting use of the property, a claimant of a right of access would be forced to bring suit within twelve years even though the government gave no indication that it contested the claimant’s right. The claimant would be compelled to sue to protect against the possibility, however remote, that the government might someday restrict the claimant’s access. The statute should not be read to create such an undesirable result.

We conclude the Michels’ claim of access to roads and trails across the refuge did not accrue until the Michels knew or should have known the government claimed the exclusive right to deny their historic access to the trails and roads across the refuge.

III.

The district court concluded that the history of disputes between the parties since 1960 indicated the Michels had notice of the government’s claim of an exclusive right to control access to the refuge land more than twelve years before filing suit. However, the allegations of the complaint would permit proof that the government abandoned and then reasserted the claim of exclusive control over access within the 12 year limitations period. As we held in Shultz v. Department of Army, 886 F.2d 1157, 1161 (9th Cir.1989) (“Shultz I ”), “[i]f the government has apparently abandoned any claim it once asserted, and then it reasserts a claim, the later assertion is a new claim and the statute of limitations for an action based on that claim accrues when it is asserted.” 2 Dismissal of the complaint under Federal Rule of Civil Procedure 12(b) was therefore improper. 3 See Jablon v. Dean Witter & Co., 614 F.2d 677, 682 (9th Cir.1980) (“When a motion to dismiss is based on the running of the statute of limitations, it can be granted only if the assertions of the complaint, read with the required liberality, would not permit the plaintiff to prove that the statute was tolled.”).

*133 According to the complaint, the government wrote a letter to the Michels in 1970 recognizing the Michels’ easement:

Amended Complaint ¶3.9 (emphasis added). The 1970 letter acknowledges the Michels’ right to access, rather than merely implying a permissive “grant” consistent with the government’s exclusive right to control access. The government’s acknowledgment of the Michels’ “historic right of access” appears to abandon any previously asserted claim of exclusive control of that right.

Although renewed disputes over access shortly after the 1970 letter may have again triggered the running of the limitations period, the complaint alleges the parties came to another agreement in 1984 allowing access by the Michels as agreed to in the 1960’s and in the 1970 letter. Id. ¶ 8.12. By expressly incorporating the 1970 letter recognizing the Michels’ “historie right of access,” the 1984 agreement could be construed as an abandonment of the government’s claim that it had the exclusive right to control access. If the government did affirm the Michels’ right of access in 1984, the present action, filed in 1992, is not barred by the twelve-year statute of limitations, and dismissal on the allegations of the complaint was inappropriate.

REVERSED AND REMANDED.

.Although we have not expressly decided this precise issue, on at least two occasions we have measured the limitations period from the time the government attempted to restrict benefits the plaintiffs previously enjoyed with respect to government properly, rather than from the time plaintiffs knew of the government's title. See, e.g., Narramore v. United States, 852 F.2d 485, 492 (9th Cir.1988); Park County v. United States, 626 F.2d 718, 720-21 (9th Cir.1980); see also Kinscherff v. United States, 586 F.2d 159, 161 (10th Cir.1978). But see Humboldt County v. United States, 684 F.2d 1276, 1280 (9th Cir.1982) (assuming that the limitations period began at the time plaintiffs learned of the government's title to land).

. This language was subsequently reaffirmed by a different panel in Shultz v. Department of Army, 10 F.3d 649, 661 (9th Cir.1993) ("Shultz II"). Although the panel granted rehearing in Shultz II, the issues presented on rehearing do not concern abandonment. In any event, Shultz I remains the law of the circuit.

. The parties dispute whether the district court’s decision constituted a dismissal under Rule 12(b) or a grant of summary judgment. Although the parties submitted materials outside of the pleadings, the district court's orders included no factual findings and made no reference to facts outside the pleading. Accordingly, we treat the decision as a dismissal under Rule 12(b).