The Wauja and Mehinako, two Aruak-speaking tribes native to the Upper Xingu River, are likely descendants of various tribes which came into the region in roughly the 9th or 10th century CE. Archaeological records going back to the time between 1000 and 1600 suggest that the people living in the region were mostly sedentary, with relatively large communities. These villages were built around a central plaza, and were defended with ditches and palisades. Archaeological evidence from the region suggests a strong relationship with a band of Aruak tribes stretching from the Upper Xingu to modern day Bolivia. It is unknown what sort of relationship the Aruak-speaking people of the Upper Xingu River had with other, Carib-speaking tribes, although the current multiethnic order in the region was in place by the 18th century.
German ethnologist Karl von den Steinen was the first European to record the existence of the Wauja tribe in 1884. He received hints that the tribe might exist (under the name Vaurá) by other indigenous peoples that he encountered on his expedition. He discovered exactly where they existed when given a map of the region by members of the Suyá tribe.
