Opinion delivered by
FERGUSON, Associate Justice.This is an appeal from the Window Rock District Court’s dismissal of Dale Nicholson Trust’s complaint for lack of subject matter jurisdiction. We vacate the judgment and remand for further proceedings.
I
The facts are taken from the Appellant’s complaint. The Appellant, Dale Nicholson Trust (Trust), derives its income from properties, assets, and business operations within the Navajo Nation. The trustee is Dale A. Nicholson, a non*423member Indian.1 The beneficiary of the Trust is an enrolled member of the Navajo Nation. The trustee’s son, Brian Nicholson, does business as Rogers Oil Company and J & R Mercantile, Inc. (Rogers and Mercantile). The Trust’s business operations are separate from Rogers and Mercantile.
All but one of the defendants are officials of the New Mexico Taxation and Revenue Department (State). The State issued separate Notices of Jeopardy Assessment of Taxes to Rogers and Mercantile, claiming that Rogers and Mercantile owed unpaid taxes connected with their gasoline businesses. The state then seized property it attributed to Rogers and Mercantile both outside and inside the Navajo Nation. The State threatened to seize property and shut down businesses of the Trust within the Navajo Nation to satisfy the Rogers and Mercantile tax bills. The State then issued several more Notices of Jeopardy Assessment of Taxes to the trustee’s son as owner of Rogers and Mercantile, causing the Trust to fear that seizure of its property and shut down of its businesses within the Navajo Nation was imminent.
On May 20,1999, the Trust filed a complaint in the Window Rock District Court for a temporary restraining order, preliminary injunction, permanent injunction, writ of replevin, and declaratory judgment against several officials of the New Mexico Taxation and Revenue Department and one Arizona official charged with tax collection (Defendants). It sought, among other things, to stop the Defendants from seizing the Trust’s property within the Navajo Nation and to order the Defendants to return any property seized while its request for injunctive relief was pending. The district court issued a temporary restraining order against the Defendants and scheduled a preliminary injunction hearing. The Defendants never entered an appearance or filed any pleading with the court. The court then denied the preliminary injunction.
Despite the denial of the preliminary injunction, the Trust moved forward with the case. Based on the Defendants’ failure to answer, The Trust filed a motion for default judgment. Without a hearing, the court dismissed the suit for lack of subject matter jurisdiction. The Court’s rationale for dismissal was that it “has no subject matter jurisdiction over the conduct of non-Indians acting in the course of their official state duties and [when] such conduct occurs off-reservation.” Judgment at 1. This appeal followed.
II
The issue in this case is whether the district court erred in dismissing a suit for lack of subject matter jurisdiction that sought to restrain state officials from seizing property located within the Navajo Nation to satisfy an alleged unpaid state tax assessment.
*424III
The Trust argues that the district court erred when it dismissed its claims for lack of subject matter jurisdiction. A district court has no discretion when ruling on its subject matter jurisdiction. If there is no jurisdiction, it must dismiss the case. We review the district court’s legal conclusions de novo. Rough Rock Community School v. Navajo Nation, 7 Nav. R. 313, 316 (Nav. Sup. Ct. 1998). While we review factual conclusions in support of the decision for clear error, id., whether there is clear error depends on how the court found the jurisdictionally relevant facts. As we have not had the opportunity to clarify how a district court should find jurisdictional facts in light of our recent case law, and as it affects this case, we do so here.
A
Absent Navajo law interpreting the Navajo Rules of Civil Procedure (Nav. R. Civ. P.), we look to federal law on similar questions for guidance. See 7 N.N.C. § 204(A) (1995 ed.) (authorizing use of federal law); Reservation Business Services v. Albert, 7 Nav. R. 123, 126 (Nav. Sup. Ct. 1995) (recognizing that Navajo Rules of Civil Procedure track federal rules). We will interpret the rules, however, consistent with Navajo Common Law. Navajo Housing Authority v. Bluffview, 8 Nav. R.402, 412 (Nav. Sup. Ct. 2003).
It is the plaintiffs responsibility to plead sufficient facts in the complaint to establish the court’s jurisdiction. See Chuska Energy Co. v. Navajo Tax Commission, 5 Nav R. 98, roo (Nav. Sup. Ct. 1986). There are two main ways to challenge the court’s jurisdiction based on factual allegations in the complaint. The defendant may file a motion to dismiss under Nav. R. Civ. P. 12(b)(1), see Nelson v. Pfizer, 8 Nav. R. 369, 373 (Nav. Sup. Ct. 2003), or the court on its own motion may question whether it has jurisdiction over the dispute.
There are two types of challenges a defendant can make under Nav. R. Civ. P. r2(b)(1). In a “facial” challenge, the defendant attacks the complaint itself as lacking facts necessary to establish jurisdiction. Menchaca v. Chrysler Credit Corp., 613 F.2d 507, 511 (5” Cir. 1980). In a “factual” challenge the defendant disputes the factual allegations in the complaint that establish jurisdiction by presenting contradictory evidence. Id.
The district court has different responsibilities in each type of challenge. In a facial challenge the court assumes the facts in the complaint to be true, with all reasonable inferences made in favor of the plaintiff. See Hubbard v. Chinle School Dist, 3 Nav. R. 167, 167, 168 (1982) (taking facts from pleadings and “matters on file” to be true for jurisdictional determination). In a factual challenge, where contradictory evidence is presented, the court weighs the evidence on both sides and makes findings of fact as it would in the merits phase of the case. Valentin v. Hospital Bella Vista, 254 F.3d 358, 363 (10th Cir. 2001). The plaintiff must prove the necessary facts for jurisdiction by a preponderance of the evidence. United States ex rel. Stone v. Rockwell International Corp., 282 F.3d 787, 798-99 (10th Cir. 2002).
*425At any time the court itself may review the complaint and find it lacks the necessary facts, or may take notice of facts entered into evidence that contradict the allegations establishing jurisdiction. Karazanos v. Madison Two Assoc., 147 F.3d 624, 626 (7th Cir. 1998); Kanzelberger v. Kanzelberger, 782 F.2d 774, 777 (7th Cir. 1986). Absent any contradictory evidence presented in the case, the court is restricted to reviewing the complaint for sufficiency, and must take all factual allegations as true and make all reasonable inferences in favor of the plaintiff. Casio, Inc. v. S.M. &R, Inc.,755 F.2d 528, 530 (7th Cir. 1985). If the plaintiff makes sufficient factual allegations, the defendant does not dispute them, and no contradictory evidence is presented, the court must take them as true and find jurisdiction. Id.
These principles must he applied in our courts within the context of federal Indian law, as interpreted by this Court and the U.S. Supreme Court. The facts the plaintiff must allege for jurisdiction over a non-Indian generally depend on the status of the land where the cause of action arose. If the case concerns tribal land2 the plaintiff needs only to allege specific facts showing that the cause of action arose on tribal land. PacfiCorp v. Mobil Oil Corp., 8 Nav. R. at 385 (Nav. Sup. Ct. 2003); Pfizer, 8 Nav. R. at 376.
If the cause of action arises on non-Indian owned fee land within the Navajo Nation the plaintiff has a higher burden. The plaintiff must fulfill one of the two exceptions set forth in Montana v. United States, 450 U.S. 544 (1981). Manygoats v. Cameron Trading Post, 8 Nav. R. 16 (Nav. Sup. Ct. 2003). Under Montana the plaintiff must allege specific facts showing that the defendant either (1) has a consensual relationship with the Navajo Nation or its members that has a nexus to the dispute, or (2) that the defendant’s conduct has a direct effect on the political integrity, economic security, or health or welfare of the Navajo Nation. Pfizer, 8 Nav. R. at 375. A hare statement that one or both of the exceptions is met, without more, is not enough.
The high threshold of Montana requires, however, that district courts allow further fact finding when the plaintiff requests it. In some cases, the plaintiff might not have the evidence available to it to properly allege fulfillment of one of the Montana exceptions without discovery or an evidentiary hearing on the jurisdictional issues. A plaintiff might be unable to establish the fact-intensive exceptions without the ability to seek evidence from the defendant through litigation. Some evidence, such as relationships between the Nation or its members and the non-Indian defendant, or information concerning the harm the defendant’s activities have on the Nation, might be in the sole possession of the defendant. We therefore instruct the district courts that they must allow discovery or an evidentiary hearing, when properly requested, in cases concerning the Montana exceptions where the defendant or the court questions *426jurisdiction.3
Because the factual allegations necessary for jurisdiction vary depending on the status of the land, it is important that the plaintiff, at the outset, allege specific facts concerning whether the cause of action arose on tribal land or non-Indian owned fee land. A statement that the dispute occurs within “the Navajo Nation,” or in “the territorial jurisdiction of the Navajo Nation” is no longer enough. Plaintiffs must affirmatively plead the status of the land.
B
The question then is whether the Trust’s complaint established the necessary specific jurisdictional facts. The court raised the issue of jurisdiction on its own, as the Defendants never entered an appearance. The court assumed that the Trust’s factual allegations were true. The district court used two factual findings to dismiss the case: (i) the Defendants were non-Indians acting in the course of their official state duties, and (2) the Defendants’ conduct was "off-reservation.”
The first finding is correct, as nothing in the complaint suggests that the Defendants threatened to seize the Trust’s property for any other reason than their pursuit of property to satisfy a state tax bill. The Defendants were acting in their capacity as agents of the New Mexico Taxation and Revenue Department.
The court’s factual finding that the conduct of the Defendants was “off-reservation” is clear error. The Trust described the previous seizure of property of Rogers and Mercantile outside the Navajo Nation, in addition to the Defendants’ threat to treat Trust property as property of Rogers and Mercantile, to justify its concern that the Defendants were about to seize its property “within the territorial jurisdiction of the Navajo Nation.” The actions the Trust sought to restrain were not the previous seizures outside the Navajo Nation, but the allegedly imminent seizure about to occur within the Navajo Nation. We assume the court used the term “off-reservation” to mean outside the territorial jurisdiction of the Navajo Nation. The district court then erred when it concluded that it lacked jurisdiction because the conduct was “off-reservation.” The remaining question then is whether the court’s legal conclusion that it lacks jurisdiction over state officials carrying out their official duties is correct.
C
State officials are a special category of non-Indians for jurisdictional purposes. State officials are not, however, outside Navajo courts’ subject matter jurisdiction merely because they are acting as agents of a state government. Office of Navajo Labor Relations ex rel. Jones v. Central Consolidated, 8 Nav. R. 234 (Nav. Sup. Ct. *4272002) (rejecting Eleventh Amendment state sovereign immunity and other jurisdictional defenses based on status as state officials). In Jones we stated that the legal doctrine of “intergovernmental immunity” barring authority over officials of other governments no longer exists. Id. at 239. The district court’s legal conclusion in this case was incorrect, as our courts do not lack subject matter jurisdiction over state officials merely because they are agents of a state.4
IV
The district court erred, and we must remand the case for further jurisdictional fact finding. The Trust brought its case before our opinions in Pfizer and other cases defined our jurisdiction over non-Indians. It made no allegations concerning the status of the land where the Defendants were to seize its property. It made no allegations concerning fulfillment of either one of the Montana exceptions. Further, the status of these Defendants, not only as non-Indians, but as state officials exercising their authority, involve unique considerations after recent U.S. Supreme Court case law. As the rules have changed, we clarify the requirements for jurisdiction over state officials and the facts necessary to sustain such jurisdiction.
A
Though we rejected an automatic bar to jurisdiction over state officials in Jones, supra, we suggested such jurisdiction depends on fulfilling Montana, even where, as in Jones, the state activity is on tribal land. We authorized a remand in Jones to consider jurisdiction in light of Nevada v. Hicks, 533 U.S. 353 (2001), to allow the Office of Navajo Labor Relations to establish more evidence on the two Montana exceptions. 8 Nav. R. at 240. If Jones applies to this case, the Trust must affirmatively establish one of the two Montana exceptions against the state defendants, even if the actions of the state officials to seize the Trust’s property were to have occurred on tribal land.
The anomaly in treatment of state official defendants in Jones arises from the U.S. Supreme Court’s decision in Hicks. In that case the court applied Montana to state official activity on tribal land, there a trust allotment. Hicks, 533 U.S. at 358. According to the U.S. Supreme Court its holding “is limited to the question of tribal-court jurisdiction over state officials enforcing state law.” Hicks, 533 U.S. at 358 n. 2. Here, the defendants are state officials allegedly enforcing state tax laws through seizure of property within the Navajo Nation.
The Trust contends Hicks does not apply because the Defendants’ seizure of the property within the Navajo Nation is beyond their authority under Navajo and federal Indian law. In Hicks, whether the state officials exceeded their authority was irrelevant to whether Montana applied. The Court applied Montana first and then analyzed the authority of the state officials later to decide whether *428the officials’ activities fulfilled the second exception. Hicks, 533 U.S. at 358-365. The U.S. Supreme Court concluded that the officials had the inherent authority to search the tribal member’s home. Based on that conclusion, it held that tribal jurisdiction was not necessary under the second Montana exception. Id. at 361-65.
The Defendants here might not have the authority under Navajo law or federal Indian law to seize the Trust’s property within Indian Country. Nevertheless, Hicks and Jones requires plaintiffs that sue state officials to first allege that the officials’ activity fulfills one of the two Montana exceptions.5 But that is not the end of the analysis, as the Hicks rule only defines the Navajo Nation’s “inherent sovereignty.”
B
The final consideration in cases involving state officials is an issue we did not consider in Pfizer: the effect of the Treaty of 1868 (Treaty between the Navajo Tribe of Indians and the United States of America, 15 Stat. 667). “Inherent sovereignty,” as defined by the U.S. Supreme Court, is only one source of authority over non-Indians. Pfizer, 8 Nav. R. at 374. The Treaty recognizes additional authority not defined as “inherent” by recent U.S. Supreme Court opinions. See Means v. the District Court of the Chinle Judicial District, 7 Nav. 383, 389-91 (Nav. Sup. Ct. 1999) (Treaty of 1868 recognizes criminal authority over non-member Indians regardless of Duro v. Reina, 495 U.S. 676 (1990)). We interpret the Treaty as our ancestors understood it. Means, 7 Nav. R. at 389.
In Article II of the Treaty of 1868 the United States set aside land for the use and occupation of the Navajo tribe of Indians, and for such other friendly tribes or individual Indians as from time to time they may be willing, with the consent of the United States, to admit among them.
Article II specifically recognizes the Navajo Nation’s authority to regulate all non-members, including non-Indians, other than certain federal employees on its lands:
[T]he United States agrees that no persons except those herein so authorized to do, and except such officers, soldiers, agents, and employees of the government, or of the Indians, as may be authorized to enter upon Indian reservations in discharge of duties imposed by law, or the orders of the President, shall ever he permitted to pass over, settle upon, or reside in, the territory described in this article.
Under the Treaty our courts have broad authority over non-Indians on land *429where the Navajo Nation has the absolute right to exclude them, which includes the power to condition their presence in conformity with our laws. Arizona Public Service Co. v. Office of Navajo Labor Relations, 6 Nav. R. 246, 249-56 (Nav. Sup. Ct. 1990). State officials are clearly not employees of “the government” authorized to enter the Navajo Nation exempt from the Treaty. Our courts then may regulate any state official activity on tribal lands.
Before Hicks the U.S. Supreme Court recognized similar treaty provisions as authority over non-Indians separate from "inherent sovereignty,” and did nothing to undermine that recognition in Hicks. In Montana itself, the U.S. Supreme Court cited the 1868 Treaty of Fort Laramie with the Crow Tribe as the source of that tribe’s authority to regulate non-Indians on tribal lands, because, like our treaty, it “obligated the United States to prohibit most non-Indians from residing on or passing through reservation lands used or occupied by the tribe.” 450 U.S. at 558; see also Atkinson Trading Company, Inc. v. Shirley, 532 U.S. 645, 650 (2001) (reiterating power of Crow Tribe to regulate non-Indians on tribal lands under treaty). The court has recognized a similar power of the Cheyenne River Sioux Tribe in its treaty. South Dakota v. Bourland, 508 U.S. 679, 687- 88 (1993). Our treaty was made in the same year as the treaties with the Crow and Sioux and contains almost identical language. The Fallon Paiute Tribe did not assert a similar treaty right in Hicks, and the U.S. Supreme Court did not consider any similar right when it announced its new rule.6
Therefore, in a situation where a plaintiff sues state officials, the general rules discussed above, supra at 5-7, apply in our courts.7 The plaintiff must allege that the cause of action arises on one of two categories of land: (1) tribal land, or (2) non-Indian owned fee land. If the activity is on the first category of land, no other showing is needed to establish jurisdiction. If on the second category, the plaintiff must allege fulfillment of one of the two Montana exceptions, with as much information as the plaintiff has before discovery or an evidentiary hearing.
V
The District court erred when it dismissed the case. Therefore its judgment *430is VACATED and the case REMANDED for proceedings consistent with this opinion. On remand, if the Trust can continue its case, see Bluffview, 8 Nav. R. at 416 (Nav. Sup. Ct. 2003) (settled expectations of parties may preclude continuation of case), it should be allowed to amend its complaint to allege (1) the status of the land on which its cause of action arises, and (2) if necessary, fulfillment of one or both of the Montana exceptions.
In its complaint the Trust alleges that the trustee is a “member” of the Navajo Nation due to various contacts with the Nation and its members. This is a legal conclusion. It is unnecessary to decide whether that is true in this decision, and we make no comment.
Tribal land includes trust land held by the United States for the Navajo Nation or its members and fee land owned by the Nation or its members within the Nation’s territory as defined by 7 N.N.C. § 254.
In cases involving tribal land, we previously stated that a district court could consider whether the defendant’s activities fulfilled the Montana exceptions. Pfizer, 8 Nav. R. at 8. We also stated that a court, when considering the exceptions, had discretion to allow discovery or an evidentiary hearing. Id. We supplement that statement here by requiring courts to allow discovery or an evidentiary hearing, when properly requested, in cases where Montana applies.
This does not mean that state officials cannot assert other non-jurisdictional immunity defenses as government officials, such as absolute or qualified immunity, in appropriate cases.
In Pfizer we read Hicks to require fulfillment of the Montana exceptions on tribal land only where “the sovereign interests of a state government enforcing state criminal law are at issue.” Pfizer, 8 Nav. R. at 377 (emphasis added). In reviewing Hicks in harmony with Jones, we must require application of Montana when state officials enforce any state law, because they are agents of the state. Seen. 6 supra. It is therefore unimportant that the officials here were to enforce state tax law instead of criminal law.
In its discussion of the second Montana exception, the Hicks majority mentioned the Treaty in a footnote. 533 U.S. at 361 n. 4. It cited Williams v. Lee, 358 U.S. 217, 221-22 (1959), a case that upheld our exclusive jurisdiction over a suit by a non-Indian against a tribal member. Id. The Hicks majority used Williams for its comparison of the Treaty with a treaty with the Cherokees at issue in Worcester v. Georgia, 31 U.S.515 (1832). Id. The Treaty had no bearing on the court’s decision to apply Montana, however, and its mention in Hicks does not affect our discussion here.
This conclusion is not inconsistent with our holding in Jones, supra. That case considered our authority over state officials under our “inherent sovereignty.” It did not consider the Treaty of 1868 as a separate source of jurisdiction. Because of the Treaty, we have jurisdiction over state officials on tribal land regardless of whether those officials’ activities fulfill the Montana exceptions.