Ngāti Paoa is descended from Paoa, whose father was Hekemaru. Paoa's paternal grandparents were Pikiao from the Te Arawa tribe, and Rereiao, a high-born Waikato woman descended from Whatihua. Paoa moved from Kaitotehe, near Taupiri in the central Waikato, to Hauraki, where he married Tukutuku, a granddaughter of Tamaterā. Paoa was the brother of Mahuta, from whom Ngāti Mahuta is descended.
Ngāti Paoa is one of five tribes of the Marutūāhu confederation, the others being Ngāti Maru, Ngāti Rongoū, Ngāti Tamaterā and Ngāti Whanaunga. The Marutūāhu tribes are all descended from Marutūāhu, a son of Hotunui, who is said to have arrived in New Zealand on the Tainui canoe. The Marutūāhu tribes are therefore part of the Tainui group of tribes. The Marutūāhu confederation is also part of the Hauraki collective of tribes.