In 1607, a ship carrying British settlers from the Virginia Company sails for North America in search of gold and other material riches. On board are Captain John Smith and Governor John Ratcliffe. A storm erupts, and Smith saves the life of an inexperienced young settler named Thomas when he falls overboard, befriending him in the process.
In the "New World", Pocahontas, Chief Powhatan's beautiful daughter, learns that her father wants her to marry Kocoum, one of his finest warriors, but a bitter and serious man. Pocahontas does not really want this marriage, and (along Winnie the Pooh, Piglet, Tigger, Rabbit, and Eeyore) asks the advice from a talking tree spirit named Grandmother Willow. Grandmother Willow tells Pocahontas to listen to her heart.
The British settlers land in Virginia and dig for gold under Ratcliffe's orders. John Smith explores the territory and encounters Pocahontas and our heroes. The two spend time together, with Pocahontas teaching John to look at the world in a different way, and to not think of her people as "savages". Back at the settlement, the Powhatan warriors and Englishmen have a skirmish, and one of the warriors is injured. The warriors retreat, and Powhatan declares that the "white men" are dangerous and that no one should go near them.
A few days later, John and Pocahontas meet again, during which John learns that there is actually no gold in the land. They agree to meet at Grandmother Willow's glade again that night. When Pocahontas and Pooh and his friends return to her village, they find that warriors from neighboring tribes have arrived to help Powhatan fight the white settlers. Back at the English fort, John tells Ratcliffe there is no gold in the land, which Ratcliffe does not believe, thinking that the natives have hidden the gold for themselves.
That night, Pocahontas' best friend Nakoma catches her sneaking off and informs Kocoum that she has gone. Meanwhile, John sneaks out of the fort, and Ratcliffe orders Thomas to follow him. Pocahontas and John meet in the glade, where Grandmother Willow convinces John to try talking to Chief Powhatan, as Powhatan had previously stated that he would be more than willing to listen. Pocahontas insists that John meet her father. When he agrees, Pocahontas is so delighted that she puts her arms around John's neck. Both Kocoum and Thomas watch from the shadows as John and Pocahontas kiss. Kocoum, full of jealousy, attacks and tries to kill John, but Thomas intervenes and kills Kocoum. The sound of the gunshot attracts several natives, and John tells Thomas to run. A group of natives take John prisoner thinking he is the murderer, and Powhatan announces that he will be executed at dawn before the war with the settlers begins.
Thomas returns to the fort and announces John's capture. Ratcliffe sees this as an opportunity to attack and rescue John at the same time, and they arrive just as John is about to be executed. Before Powhatan can deliver the fatal blow to John' head, Pocahontas throws herself over John and tells her father that if he kills him, he's going to have to kill her as well. Powhatan orders her to stand back, but Pocahontas refuses and admits her love for him to the surprise of everyone else. She tells her father that this is what the path of hatred has brought and that she has chosen her path and it's time he chooses his. After thinking about what Pocahontas has said, he lowers his club and announces that the hatred will end and that no killing will come from him. The settlers and the natives then lower their weapons. Powhatan orders John to be released and when he is, Pocahontas rushes into his arms. Ratcliffe, seeing an opportunity, orders the settlers to fire anyway, but they refuse. Ratcliffe grabs a gun and aims it at Powhatan. John sees this and pushes him out of the way as Ratcliffe fires. The bullet hits John in the stomach and he falls to the ground. The settlers turn on Ratcliffe, capturing him and sending him back to England to await punishment for high treason.
John survives his gunshot wound, but must go back to England for proper medical treatment or else he will die. Pooh and his friends decided to go back to England with him too. As he is about to be loaded onto the ship, John tells the settlers to wait because Pocahontas promised she would show up. At that moment, John and the settlers see her and her people arrive, carrying baskets of food for them. Pocahontas goes to John and gives him a pouch of Grandmother Willow's bark, telling him it will help with the pain. Powhatan then walks up and takes off his tribal shawl. As he lays it over John, he tells him that he will always be welcome among the natives. He then thanks John for heroism and calls him his brother. John then asks Pocahontas to come back to England with him. She looks at her father who tells her that she must choose her path. Pocahontas then tearfully tells John that she belongs with her people. John then tells her he'll stay and Pocahontas tell him he must go. John tells her that he can't leave her and Pocahontas says he never will and no matter what happens, she'll always be with him. The two of them kiss and hold hands until John is taken away. As the ship sails away, Pocahontas runs to the cliff and when John sees her standing there, he waves to her by the tribal way she taught him and Pocahontas waves back.
- This is a PAL film with PAL bits from The Many Adventures of Winnie the Pooh, Pooh's Grand Adventure: The Search For Christopher Robin, Piglet's Big Movie, and Pooh's Heffalump Halloween Movie and NTSC bits from The Tigger Movie, Winnie the Pooh: A Very Merry Pooh Year, and Pooh's Heffalump Movie.
- The storyline continues in Pooh's Adventures of Pocahontas II: Journey To a New World.
- Pooh and his friends met Poachontas and John Smith again and faced Governor Ratcliffe again in the Walt Disney World version of Winnie The Pooh In Fantasmic!.