The tribe's ancestor and namesake was Waitaha. He was a son of Hei who was the uncle of Tamatekapua. Their tribe was Ngāti Ohomairangi of Ra'iātea Island. After engaging in war with Uenuku, over 30 members of the tribe migrated to New Zealand onboard the Ngā rākau rua a Atuamatua, named in honour of Waitaha and Tamatekapua's grandfather. They encountered the sea creature named Te Parata that was summoned by the people on the Tainui. They were saved from it by a great mythical shark, and in its honour renamed their canoe and themselves to Te Arawa. Upon arriving to the North Island, they explored the coast from Cape Runaway to the Hauraki Gulf. The priest Ngātoroirangi performed rituals to conceal the tribe's atua and guardians in the landscape, brought to the new island from the old marae at Taputapuātea. They gathered new supplies and moved on, deciding that the western Bay of Plenty would be the best place to settle. The crew began claiming parts of the land for their descendants. Hei claimed the area between the Pāpāmoa mountain and the Coromandel Range for his son Waitaha. Waitaha indeed lived close to Maketū, along with Tapuika.
Over 13 generations ago, Te Arawa iwi including the Waitaha were pushed out of Maketū by Te Rangihouhiri. It took several generations before Ngāti Whakaue and the descendants of Waitaha and Tapuika managed to win back Maketū, and negotiate an uneasy truce. The early 1820s saw continued arrivals of many European migrants to New Zealand, bringing diseases which the native Māori had no immunity to, owing to the fact that the two groups had been separated for all of history up until that point. These diseases would wipe out entire villages, and many bodies would lie untouched and unburied out of fear of contagion and infection. These places today are tapu, or used as cemeteries. These plagues such as the coughing death, or Te Rewharewha, impacted Te Arawa even though no Europeans had yet visited their region; so too did the arrival of muskets offset their way of life, when Ngāpuhi under Hongi Hika slaughtered many Te Arawa tribes at Lake Rotoehu in 1823. Ngāpuhi were assisted by Te Rangihouhiri's descendants, Ngāi Te Rangi. Te Arawa were so demoralised during these times, that they considered moving south to Kapiti Island for protection under Ngāti Toa. In 1829, five generations after the battle with Te Rangihouhiri, the first European migrant to the region, Phillip Tapsell, brought muskets to the iwi. Te Arawa worked against Ngāi Te Rangi and Ngāti Awa in jealousy and competition for the muskets. All tribes would be constantly working to weave flax the fastest, the weavings in exchange for the weapons. One skirmish between the tribes resulted in the Ngāti Hauā chief Te Waharoa destroying the trading station at Maketū. Many such skirmishes all culminated into the battle of Te Tūmū on 20 April 1836. Te Arawa suffered greatly, but defeated Ngāi Te Rangi and regained Maketū. They extended their territory from Wairaki at Pāpāmoa to Te Kaokaoroa at Matatā. Some months later, Te Waharoa tried to avenge the battle on Ngāi Te Rangi's behalf by attacking Te Arawa's Te Mātaipuku–Ōhinemutu pā, the gateway of which was named Pūkākī.
