OPINION
ERVIN, Chief Judge:Richmond, Fredericksburg and Potomac Railroad Company brought this action under the Quiet Title Act, 28 U.S.C. § 2409a, to quiet title in certain real property in northern Virginia. We find, as did the district court, that the action is barred by the Quiet Title Act’s statute of limitations. Therefore, we affirm the district court’s dismissal of the action.
I.
In 1938, the United States Secretary of the Interior and Richmond, Fredericksburg and Potomac Railroad Company (RF & P) executed an indenture by means of which various property rights in 17 parcels of land in the vicinity of the Mount Vernon Memorial Highway were exchanged. Having authorized the construction of this highway in 1928, Congress in 1930 incorporated it into the larger George Washington Memorial Parkway project. Act of May 29, 1930, 46 Stat. 482. The 1930 Act provided that the George Washington Memorial Parkway (the Parkway) was to be administered by what is now the National Park Service. Since 1953 the Parkway has been a part of the National Park System.1 In its administration of the Parkway, the National Park Service is under a Congressional mandate to conserve the highway’s scenic value. 16 U.S.C.A. § 1 (West 1974) (as amended). The National Park Service executes this mandate by planting and landscaping within existing Parkway boundaries and by acquiring scenic easements over adjoining lands.
The 1938 indenture sought to resolve doubts concerning the boundaries between land claimed to be owned by both parties and to settle controversies as to their respective rights, titles, interests and estates. The government wanted to protect the views from the Mount Vernon Memorial Highway, while RF & P sought to clear its title to areas it needed for the expansion of Potomac Yard and other railroad-related facilities. In the indenture, the United States quitclaimed to RF & P a tract, la-belled “Area 3,” encompassing roughly 40 acres near Four Mile Run just west of the Parkway’s original route. The land at issue in this appeal constitutes a portion of Area 3 which underlies a section of RF & P’s main line between Washington, D.C. and Richmond, Virginia, and part of RF & P’s Potomac Yard.
The quitclaim was not, however, an unconditional transfer of the land. The indenture specifies that the transferred land is subject to a use restriction, which provides that the property is “to be used by [RF & P], its successors and assigns, solely for the construction, maintenance and operation of its main line tracks and ways and a freight yard in connection therewith.” This restriction is further restated as a covenant, of which the burden is to run with Area 3 and the benefit is to run with adjacent lands owned by the United States. The covenant states that RF & P “will not use ... Area 3 for any purpose other than the construction, maintenance and opera*768tion by it of its main line railroad tracks and ways and a freight yard in connection therewith.”
In 1938, Area 3 was separated from the Parkway by two other parcels of land. When Washington National Airport was created, the segment of the Parkway that paralleled Area 3 was moved to the west to its present location, so that the Parkway now crosses land that was within the bounds of Area 3 at the time of the indenture. In 1975 and 1977, the Washington Metropolitan Transit Authority purchased a narrow strip of Area 3 from RF & P for the construction of a Metrorail line serving stops in northern Virginia. This Metrorail corridor adjoins Parkway land administered by the National Park Service. As a result, the traffic lanes of the Parkway are now separated from the 36-acre portion of Area 3 that remains in RF & P's control only by a narrow strip of Parkway land and by the Metrorail right of way.
Recently, commercial developers in whose enterprises RF & P has an interest have proposed to construct on the land at issue two major projects near the Washington National Airport. Alexandria city officials and citizen groups have opposed these projects, fearing that they will destroy the Parkway area as originally envisioned by Congress and create major traffic congestion, and have made efforts to block the development entirely. As a compromise solution, the National Park Service, while reasserting the effectiveness of the 1938 quitclaim restriction and covenant on Area 3, has offered to negotiate with the developers and RF & P. The National Park Service proposes to drop the railroad use restriction on Area 3 if the developers will give up their right2 to build an interchange with the Parkway.
Refusing to negotiate, RF & P filed this action to quiet title in the disputed land in the United States District Court for the Eastern District of Virginia at Alexandria. The named defendants were the United States, the Metropolitan Washington Airports Authority, and the Washington Metropolitan Area Transit Authority. RF & P sought a declaration that the use restriction in the indenture has ceased to be effective or, in the alternative, that the restriction is presently satisfied by RF & P’s use of a portion, rather than the entirety, of the property for railroad purposes. The government filed a motion to dismiss on the grounds that subject matter jurisdiction was lacking by reason of the statute of limitations in the Quiet Title Act, 28 U.S.C. § 2409a(g).
The district court, having found that the Section 2409a(g) statute of limitations clearly barred a quiet title action in this case, granted the government’s motion to dismiss. RF & P appeals to this court.
II.
When a Rule 12(b)(1) motion challenge is raised to the factual basis for subject matter jurisdiction, the burden of proving subject matter jurisdiction is on the plaintiff. Adams v. Bain, 697 F.2d 1213, 1219 (4th Cir.1982). In determining whether jurisdiction exists, the district court is to regard the pleadings’ allegations as mere evidence on the issue, and may consider evidence outside the pleadings without converting the proceeding to one for summary judgment. Id.; Trentacosta v. Frontier Pacific Aircraft Indus., 813 F.2d 1553, 1558 (9th Cir.1987). The district court should apply the standard applicable to a motion for summary judgment, under which the nonmoving party must set forth specific facts beyond the pleadings to show that a genuine issue of material fact exists. Trentacosta, supra, 813 F.2d at 1559 (citing Celotex Corp. v. Catrett, 477 U.S. 317, 323-24, 106 S.Ct. 2548, 2552-53, 91 L.Ed.2d 265 (1986)). The moving party should prevail only if the material jurisdictional facts are not in dispute and the moving party is entitled to prevail as a matter of law. Trentacosta, supra, 813 F.2d at 1558. A district court order dismissing a case on the grounds that the undisputed facts establish a lack of subject matter jurisdiction is a legal determination subject to de novo ap*769pellate review. Revene v. Charles County Comm’rs, 882 F.2d 870, 872 (4th Cir.1989); Shultz v. Dept. of the Army, 886 F.2d 1157, 1159 (9th Cir.1989).
The Quiet Title Act (the Act) is a limited waiver of the sovereign immunity of the United States, by virtue of which actions may be brought to quiet title to lands in which the United States “claims an interest.”' 28 U.S.C.A. § 2409a(a) (West 1978). The Act provides, however, that the waiver of immunity expires within twelve years of the date that the claim accrued. The claim accrues on the date that the plaintiff or his predecessor in interest “knew or should have known of the claim of the United States.” 28 U.S.C.A. § 2409a(g) (West Supp.1991). Because the limitations period represents a condition on the waiver of federal sovereign immunity, it is a jurisdictional prerequisite to suit and is to be construed narrowly in favor of the government. Block v. North Dakota, 461 U.S. 273, 282-83, 103 S.Ct. 1811, 1817-18, 75 L.Ed.2d 840 (1983). See, e.g., Fulcher v. United States, 696 F.2d 1073, 1078 (4th Cir.1982); Knapp v. United States, 636 F.2d 279, 282 (10th Cir.1980).
A strict construction of the statute of limitations in the Quiet Title Act conforms to Congress’s intent in adding the limitations provision to the Act. The Act “grandfathered in” causes of action that accrued during the 12-year period between 1960 and 1972 (when the statute was enacted), but created no cause of action to quiet title for any title claim that accrued prior to 1960. See H.R.Rep. No. 1559, 92d Cong., 2d Sess., reprinted in 1972 U.S.Code Cong. & Admin.News 4547, 4550; see also Knapp, supra, 636 F.2d at 282. Summarizing the history of the legislation that became the Quiet Title Act, the Supreme Court noted that Congress added this provision in response to Executive Branch concern with limiting costly litigation over stale land claims. Block, supra, 461 U.S. at 282-84, 103 S.Ct. at 1817-18.
The merits of a quiet title claim are irrelevant to the operation of the limitations bar. Deakyne v. Dept. of the Army Corps of Engineers, 701 F.2d 271, 274 n. 6 (3d Cir.), cert. denied, 464 U.S. 818, 104 S.Ct. 78, 78 L.Ed.2d 89 (1983); Government of Guam v. United States, 744 F.2d 699, 701 (9th Cir.1984). The interest claimed need not amount to full legal title in the United States. As long as the interest claimed is a “cloud on title,” or a reasonable claim with a substantial basis, it constitutes a “claim” for purposes of triggering the twelve-year statute of limitations. Economic Development & Industrial Corp. v. United States, 720 F.2d 1, 3 (1st Cir.1983). Accord Knapp, supra, 636 F.2d at 282; Vincent Murphy Chevrolet Co. v. United States, 766 F.2d 449, 452 (10th Cir.1985); California v. Yuba Goldfields, Inc., 752 F.2d 393, 397 (9th Cir.), cert. denied, 474 U.S. 1005, 106 S.Ct. 526, 88 L.Ed.2d 458 (1985). The crucial issue in the statute of limitations inquiry is whether the plaintiff had notice of the federal claim, not whether the claim itself is valid. Government of Guam, supra, 744 F.2d at 701.
RF & P argued before the district court that a proceeding on the merits of the government’s claim was nevertheless required because genuine issues of material fact existed concerning (1) the interpretation of the use restriction, and (2) the point in time at which the government’s claim accrued. The district court correctly determined that, despite the evidence RF & P presented, no genuine issue of material fact existed since the 1938 indenture gave RF & P actual notice of the government’s unambiguously defined interest in restricting the uses of Area 3. See Vincent Murphy, supra, 766 F.2d at 450-52 (restrictions in quitclaim deeds from United States to plaintiff provided actual notice of use restrictions); Hart v. United States, 585 F.2d 1280, 1283 (5th Cir.1978), cert. denied, 442 U.S. 941, 99 S.Ct. 2882, 61 L.Ed.2d 310 (1979) (deeds conveying land to United States provided actual notice to sellers).
RF & P also contended that the National Park Service’s recent reassertion of the Area 3 restrictions is a “new claim” which is broader in scope than the claim asserted in the indenture, and that therefore in 1938 RF & P had no reason to know of this *770broader claim. Implicit in RF & P’s contention is the assertion that the government abandoned its claim prior to reasserting it. See Shultz v. Dept. of the Army, 886 F.2d 1157, 1161 (9th Cir.1989) (stating in dictum that apparent abandonment followed by reassertion constitutes a new claim for limitations purposes). Moreover, RF & P argued that the 1938 indenture could not be said to have put the railroad on notice of the government’s claim so long as RF & P could reasonably have doubted the merits of that claim. Citing general property law principles, the overall pattern of exchanges effected by the indenture, and events surrounding the indenture’s execution, RF & P maintained that in 1938 it reasonably believed that the use restriction was temporary, terminable in the event that changed conditions no longer justified it.
The use restriction in the 1938 indenture is clear and unambiguous. The United States quitclaimed Area 3 to RF & P on the explicit condition that the land be used solely for railroad purposes. The restriction was expressed as a covenant, the burden of which was to run with the land, i.e., Area 3. Covenants that run with the land are not temporary unless they provide for conditions of termination or expiration. It is clear, as the district court found, that RF & P knew what the nature of this restriction was in 1938, and that the National Park Service is now asserting that same restriction. Assuming arguendo that RF & P did not know the exact nature of the government’s claim in 1938, it still could not escape the limitations bar, for all that is necessary for accrual is “a reasonable awareness that the Government claims some interest adverse to the plaintiff’s.” Knapp, supra, 636 F.2d at 283 (citing United States v. Kubrick, 444 U.S. 111, 100 S.Ct. 352, 62 L.Ed.2d 259 (1979)) (emphasis added).
Moreover, there is no evidence that the government has ever extinguished or relaxed the use restriction, or abandoned its claim to the continued power of restriction over Area 3. Neither the relocation of the Parkway nor the construction of the Metro-rail line, which RF & P cited as non conforming uses, violated the restrictions placed on the various land parcels transferred in the 1938 indenture. These uses do not conflict with the Congressional purpose of preserving scenic beauty along the Parkway. In contrast, the commercial use RF & P seeks would interfere with this purpose and certainly justifies the government’s reassertion, as to that proposed use, of the right to restriction it has held since 1938. To hold that the limitations period did not begin to run until conditions had changed and the government reasserted its claim would be in effect to extend the limitations period indefinitely, in contravention of Congress’s expressed intent. See Block, supra, 461 U.S. at 287, 103 S.Ct. at 1819-20; Vincent Murphy, supra, 766 F.2d at 452.
The operation of the statute of limitations is hardly harsh in this case. It simply means that RF & P cannot get fee simple title to Area 3 for nothing. Having knowingly covenanted not to develop this land, RF & P cannot avoid negotiation as a necessary condition of altering the land use restriction on Area 3. The district court’s order is
AFFIRMED.
. See Act of Aug. 8, 1953, ch. 384, 67 Stat. 496, codified as amended at 16 U.S.C.A. § lc(aj (West 1974); see abo Act of Aug. 18, 1970, 84 Stat. 825, codified at 16 U.S.C.A. § la-1 (West 1974).
. The government previously traded the right to an interchange with the Parkway to developers in exchange for some wetlands south of Alexandria that were threatened with development.