In the past, the goddess Te Fiti created life on Earth and became an island. Her heart, a pounamu stone, was stolen by the demigod Maui, who intended to give the heart to humanity as a gift. However, as he made his escape, he was attacked by the lava demon Te Ka, causing the heart and Maui's magical fishhook to become lost at sea.
A millennium later, Moana Waialiki, the daughter of Chief Tui and Sina on the island of Motunui, is chosen by the ocean to restore the heart. Years later, the villagers discover the fish and vegetation dying out, and Moana suggests sailing beyond the reef to find more fish. However, her father forbids it. Later, Moana's grandmother, Tala, shows her a secret cave, where she discovers their ancestors used to be voyagers. Gramma Tala tells Moana that after Maui stole Te Fiti's heart, the world was cursed by Te Ka to slowly be consumed in darkness. Giving Moana the heart, Tala tells Moana to go and restore it. Shortly afterwards, Tala falls ill and passes away.
Moana, following her grandmother's wishes, departs in a sailboat, accompanied by a rooster named Heihei, in order to find Maui. Knocked unconscious by a typhoon, Moana awakens on an island inhabited by Maui, who steals Moana's sailboat and abandons Moana. With help from the ocean, Moana catches up to Maui and demands that he help her restore the heart, but he refuses, fearing the dark creatures it may attract.
After escaping a band of pygmy pirates called Kakamora, Maui agrees to help restore the heart, but only after he retrieves his fishhook, which allows him to transform. The two travel to Lalotai, the Realm of the Monsters, where the fishhook is being held by the giant coconut crab Tamatoa. Maui manages to retrieve the fishhook, but finds he is unable to transform properly due to being out of practice. After escaping Tamatoa, Maui reveals to Moana that he was born to human parents who abandoned him as an infant, and he was raised by the gods, who granted him his powers. With encouragement from Moana, Maui learns how to properly use the fishhook, and he in turn teaches her to sail and navigate.
Arriving at Te Fiti, the two are attacked by Te Ka. During the ensuing confrontation, Maui's fishhook is damaged and the two are repelled out to sea. Fearing that returning to battle Te Ka will result in the destruction of his fishhook, Maui abandons Moana. A distraught Moana returns the heart to the ocean, begging it to choose another person to return it to Te Fiti. However, the spirit of Tala encourages Moana to find her true calling within herself, reinvigorating Moana to retrieve the heart and return to Te Fiti. Te Ka attacks her, but Maui returns, having had a change of heart, and distracts the lava demon, causing his fishhook to be destroyed. Reaching the island of Te Fiti, Moana realizes that Te Ka is actually a cursed Te Fiti. She tells Te Ka to remember who she truly is, placating the goddess and allowing Moana to restore the heart
With her heart restored, Te Fiti returns and grants Moana and Maui a new canoe and a new fishhook. Moana and Maui bid farewell, and Moana returns to her island, where she is crowned the new chief. With the curse lifted, the villagers begin voyaging again and set sail in search of new islands, with Maui accompanying them in hawk form.