Plaintiffs, members of the Yakama Indian Nation, brought this action to prevent defendants, Washington state officials and officers (the “State”), from applying state truck license and permit fees to members of the Yakama tribe. Plaintiffs claim that the fees violate the right to use public highways granted to the Yakama tribe under the Yakama Treaty. The district court granted summary judgment to the Yakama Indian Nation on the ground that the phrase “in common with,” as used in the Treaty in reference to the highway right, has been construed in Treaty fishing rights cases to bar the State *1402from imposing truck license and permit fees on Yakama Indians. The State appealed. We have jurisdiction under 28 U.S.C. § 1291, and we reverse and remand.
FACTS
The individual plaintiffs are Yakama Indians who operate logging trucks to haul logs from tribal timber sales on reservation lands to off-reservation markets. They have been issued traffic citations by defendant traffic officers for failing to pay licensing fees and obtain truck permits, as required by Washington state law.1 Plaintiffs brought this action against defendants for declaratory relief and damages under 42 U.S.C. § 1983, and for declaratory and injunctive relief to prevent defendants or other similarly situated officers from interfering with plaintiffs’ alleged right under the Treaty to use the state’s highways without having to pay the contested fees.2
Washington state law requires motor vehicles to be registered, with an accompanying registration fee. Washington further requires trucks to be licensed according to gross weight, with higher weights bearing higher licensing fees. Indian-owned trucks have never been exempt from these fees.3
The Yakamas claim that the following underlined portion of the 1855 Treaty between the United States government and the Yakama Tribe (“the Treaty”) gives the Yakama Indians the right to haul tribal timber to market over state highways without having to pay the contested fees:
And provided, That, if necessary for the public convenience, roads may be run through the said reservation; and on the other hand, the right of way, with free access from the same to the nearest public highway, is secured to them; as also the right, in common with the citizens of the United States, to travel upon all public highways.
Treaty, Article III, ¶ 1.
No prior decision has interpreted the Treaty’s highway right. The Yakamas claim that their interpretation of the highway right is mandated by the Supreme Court’s interpretation of the Treaty’s fishing rights:
The exclusive right of taking fish in all the streams, where running through or bordering said reservation, is further secured to said confederated tribes and bands of Indians, as also the right of taking fish at all usual and accustomed places, in common with citizens of the Territory....
Treaty, Article III, ¶2 (emphasis added). The Supreme Court has interpreted the fishing rights to bar the State from imposing generally applicable regulations, such as fees for fishing with nets, on the Yakama Indians despite the phrase “in common with citizens of the Territory.” See, e.g., Tulee v. Washington, 315 U.S. 681, 684, 62 S.Ct. 862, 864, 86 L.Ed. 1115 (1942).
The district court granted summary judgment to the Yakamas, holding that it “cannot construe the ‘in common with’ language as it applies to Treaty travel rights any differently than this phrase has been construed regarding the Treaty right to fish.” Cree v. Waterbury, 873 F.Supp. 404, 418 (E.D.Wash.1994).
DISCUSSION
A. Standard of Review and Burden of Proof
This court reviews de novo a district court’s grant of summary judgment. Fort *1403Belknap Indian Community v. Mazurek, 43 F.3d 428,432 (9th Cir.1994).
State tax laws4 applied to Indians outside of Indian country, such as those at issue here, are presumed valid “[ajbsent express federal law to the contrary.” Mescalero Apache Tribe v. Jones, 411 U.S. 145, 148-49, 93 S.Ct. 1267, 1270-71, 36 L.Ed.2d 114 (1973). A treaty can constitute such an express federal law. U.S. v. Washington, 520 F.2d 676 (9th Cir.1975).
The State argues that the Yakamas bear the burden of proving a tax exemption in the Treaty. However, in interpreting a treaty between the United States and an Indian tribe, the court must interpret the treaty “in the sense in which [the treaty language] would naturally be understood by the Indians.” Washington v. Washington Commercial Passenger Fishing Vessel Ass’n (“Fishing Vessel”), 443 U.S. 658, 675-76, 99 S.Ct. 3055, 3067, 61 L.Ed.2d 823 (1979) (internal quotation marks omitted). Treaties are “broadly interpret[ed]” in the Indians’ favor. Id.
B. The Fishing Rights Cases Do not Define the Term “in Common With.”
Whether the Yakama Treaty exempts the Yakamas from highway user fees depends on the parties’ intent when they signed the treaty. See, e.g., Fishing Vessel, 443 U.S. at 675, 99 S.Ct. at 3069. To determine the parties’ intent, the court must examine the treaty language as a whole, the circumstances surrounding the treaty, and the conduct of the parties since the treaty was signed. Id.; see also Oliphant v. Suquamish Indian Tribe, 435 U.S. 191, 206-08, 98 S.Ct. 1011, 1019-21, 55 L.Ed.2d 209 (1978); Choctaw Nation of Indians v. United States, 318 U.S. 423, 431-32, 63 S.Ct. 672, 678, 87 L.Ed. 877 (1943); Seufert Bros. Co. v. United States, 249 U.S. 194, 198-99, 39 S.Ct. 203, 205, 63 L.Ed. 555 (1919).
The district court held that it was unnecessary to address evidence of the parties’ intent. Cree v. Waterbary, 873 F.Supp. 404, 423-24 (E.D.Wash.1994). The district court held that the fishing rights cases construed the “in common with” language of the Treaty to give the Indians rights beyond those of ordinary citizens. Id. at 422-23. The district court held that the fishing rights cases were applicable to this ease because the right to travel upon public highways was “sufficiently comparable” to the right to fish. Id. at 425. Therefore, the district court held that the “in common with” language “unambiguously ... gives the Yakama Indian Nation the right to exercise its nonexclusive rights without being subject to licensing or permitting fees.” Id. at 426.
However, the fishing rights cases have not found the “in common with” language to support the conclusion that Indians may exercise treaty rights without paying generally applicable fees. In each case involving the Treaty fishing rights, the Supreme Court has held that the Yakama Indians have special fishing rights “despite” the phrase “in common with.” E.g. Tulee, 315 U.S. at 684, 62 S.Ct. at 864 (holding that the state could not require Yakama Indians to purchase licenses for using traditional nets to catch fish). In these eases, the Supreme Court looked at the language of the fishing rights, the historical context, and the behavior of the parties after the treaty to determine the parties’ intent. E.g., United States v. Winans, 198 U.S. 371, 381, 25 S.Ct. 662, 664, 49 L.Ed. 1089 (1905); Fishing Vessel, 443 U.S. at 677-81, 99 S.Ct. at 3070-72. It is true that in each case, the Supreme Court held that the parties could not have intended the Treaty to allow Yakama Indians to retain no greater rights than non-Indian citizens. However, the district court erred in holding that these cases defined the term “in common with” to mean that no fees could be charged for the exercise of a Treaty right.
By viewing the historical context of the Treaty, the courts in the fishing right cases *1404have found that the Yakama Indians did not intend the “in common with” language “to limit their right to fish in any way.” United States v. Washington, 384 F.Supp. 312, 333 (W.D.Wash.1974), aff'd, 520 F.2d 676 (9th Cir.1975). Rather, the Fishing Vessel district court noted that
the United States negotiators promised, and the Indians understood, that the Yakamas would forever be able to continue the same off-reservation food gathering and fishing practices as to time, place, method, species and extent as they had or were exercising. The Yakamas relied on these promises and they formed a material and basic part of the treaty and of the Indians’ understanding of the meaning of the treaty.
Id. at 381 (citations omitted).
In Winans, the Supreme Court held that the fishing clause gave the Yakamas an easement over privately owned land so that the Yakamas could use their old trails to reach their “usual and accustomed” fishing sites. Winans, 198 U.S. at 381, 25 S.Ct. at 664. The Court held that the fishing right, reserved “in common with citizens of the territory,” was “not exclusive in the Indians,” but gave the Yakamas the easement because “[n]o other conclusion would give effect to the treaty.” Id.; see also Seufert Bros. v. United States, 249 U.S. 194, 195, 39 S.Ct. 203, 204, 63 L.Ed. 555 (1919) (extending the Winans easement to land not ceded in the Yakama Treaty).
In Fishing Vessel, the Court construed the fishing right to guarantee the Yakamas a fixed share of available fish, rather than an “equal opportunity” to catch fish on the same grounds as non-Indians. 443 U.S. 658, 679-81, 99 S.Ct. 3055, 3071-72. The Court stated,
It is true that the words ‘in common with’ may be read either as nothing more than a guarantee that individual Indians would have the same right as individual non-Indians or as securing an interest in the fish runs themselves.... But we think greater importance should be given to the Indians’ likely understanding of the other words in the treaty and especially the reference to the ‘right of taking fish’— a right that had no special meaning at common law but that must have had obvious significance to the tribes relinquishing a portion of their pre-existing rights to the United States in return for this promise.
Id. at 677-78, 99 S.Ct. at 3070-71 (emphasis in original). Again, the Court found that the fishing right gave Yakama Indians greater rights in spite of, not because of, the “in common with” language. The Court also noted that “when the treaties were negotiated, neither party realized or intended that their agreement would determine whether, and if so how, a resource that had always been thought inexhaustible would be allocated between the native Indians and the incoming settlers when it later became scarce.” Id. at 669, 99 S.Ct. at 3081.
It is clear from the fishing right cases that “in common with” does not by itself define the nature of the right. These eases hold only that the phrase “in common with” does not limit Tribal rights to those held by others; the Supreme Court determined the nature of those rights not by parsing the term “in common with,” but by examining other words in the Treaty, their historical context, practical construction of the right, and the parties’ intent.
In contrast, there has been no finding of what the Indians understood their right to use government-built highways to encompass. Therefore, the district court erred when it held that the “prior fishing decisions define the meaning of ‘in common with’ unambiguously as giving ... the Yakama Indian Nation the right to exercise its nonexclusive rights without being subject to licensing or permit fees.” The district court must undertake a factual inquiry into the intent and understanding of the parties at the time the Treaty was signed to determine the meaning of the highway right. Cree, 873 F.Supp. at 426.
C. Constitutional Right to Travel.
The State argues that the highway right gives the Yakamas only a right to travel upon public highways identical to the constitutional right to travel. This interpretation *1405of the highway right requires the Yakamas to pay the same fees as other U.S. citizens,
The Yakamas argue that this interpretation would result in the highway right being mere surplusage, rather than a bargained-for right, and would violate the rule of contract construction that “a court must give effect to every word or term employed by the parties and reject none as meaningless or surplusage in arriving at the intention of the contracting parties.” United States v. Hathaway, 242 F.2d 897, 900 (9th Cir.1959).
The State points out that in the nineteenth century, Indians were not U.S. citizens and did not possess citizenship rights. Elk v. Wilkins, 112 U.S. 94, 5 S.Ct. 41, 28 L.Ed. 643 (1884) (Indians not citizens and therefore not entitled to voting rights). The State argues that the Treaty gave the Indians a right they would not have had otherwise: a right to use the off-reservation roads. We do not hold as a matter of law that the highway right must be interpreted to bar the State from imposing truck fees on the Yakama Indians to prevent the highway right from being mere surplusage. However, we cannot hold as a matter of law that the Treaty gave the Yakamas rights no greater than those of any non-Indian U.S. citizen. A factual investigation into the historical context and parties’ intent at the time the Treaty was signed is necessary to determine the precise scope of the highway right.5
CONCLUSION
The district court erred in holding as a matter of law that the Treaty bars the imposition of truck fees on Yakama Indians. We REVERSE and REMAND to the district court to examine the Treaty language as a whole, the circumstances surrounding the Treaty, and the conduct of the parties since the Treaty was signed in order to interpret the scope of the highway right.
. The State argues that the fees "implement federal highway financing policy,” and that consequently the fees are valid unless the Treaty creates a "definitely expressed” exemption. Confederated Tribes of the Warm Springs Reservation v. Kurtz, 691 F.2d 878, 881-82 (9th Cir.1982). The State presents no authority for this court to find that the state-imposed truck fees should be judged according to the standard for federal fees.
.The contested fees are: Wash.Rev.Code §§ 46.16.070 (requiring vehicle tonnage licenses); 46.16.135 (providing for monthly payment of tonnage licenses and noting that operation of vehicle after expiration of monthly license is traffic infraction); 46.44.047 (special log tolerance weight permits); 46.44.095 (annual additional tonnage permits). Plaintiffs do not challenge the State’s ability to impose weight regulations upon the Yakamas, but assert that the State cannot impose citations solely due to plaintiffs’ failure to obtain the weight licenses and permits where they are otherwise in compliance with the weight regulations.
. The district court held that the fees were “taxes” under 28 U.S.C. § 1341. Therefore, due to the Tax Injunction Act, the district court held that it did not have subject matter jurisdiction over the claims of the individual plaintiffs. Because the Yakama Indian Nation could bring these claims, the district court granted its motion to intervene as plaintiff. See Cree v. Waterbury, 873 F.Supp. 404, 409 (E.D.Wash.1994).
. The State notes that the license and permit fees are now prorated to reflect the amount of time Indian trucks are used on highways outside the Yakama Indian Reservation.
. The State also argues that the district court erred in finding the highway right of Article III, ¶ 1 to be “analogous” to and "intertwined” with the fishing right of Article III, ¶ 2. 873 F.Supp. at 420-21. The district court stated that "the right to travel and the right to take fish are inextricably intertwined. The right to fish obviously depended upon the ability of the Yakamas to travel to various sites.” Cree, 873 F.Supp. at 421. Because we hold that the district court erred in applying the fishing right cases to interpret the highway right, it is immaterial whether or not the rights are "analogous” and "intertwined.” Therefore, we do not need to address the State's argument.