Tony Hillerman’s use of “Division of Law and Order” as part of the Navajo Nation's tribal authority is an intentional “mistake,” as there is no Division of Law and Order under the Navajo Tribal Council. Rather, the Navajo Nation maintains the Division of Public Safety, under which are several branches, including the Navajo Police Department. In addition, Hillerman makes a distinction between local Law and Order, which occurs at the tribal and agency level, and federal Law and Order, which occurs at the bureau level and emanates from Washington, D.C.
Law and order, as understood from a Western perspective, was established among the Navajo by an 1849 Treaty between the United States and the Navajo. In exchange for Navajo recognition of U.S. authority, access to and passage through Navajo lands, and the establishment on Navajo lands of U.S. military posts, the U.S. would provide "gifts" to the Navajo. Later, from the time the U.S. acquired the territory of New Mexico from Mexico during the Mexican-American War (1846-48), "law enforcement" among the Navajo was handled primarily by the U.S. military or by the Federal Government’s Branch of Law and Order. This included the forced relocation of the Navajo from their tribal lands during the Long Walk and internment at Bosque Redondo near Fort Sumner, New Mexico.
Today, the Navajo Police Department is a law enforcement agency on the Navajo Nation Reservation, originally established in 1872, four years after the Navajo were released from captivity in Fort Sumner. Despite it's initial success, the Navajo Tribal Police was dissolved in 1975. The Navajo Nation Police were not reestablished until 1959 when the Navajo Tribal Council requested its reinstatement.