Puss in Boots is a talking cat named for his wearing boots and is a fugitive on the run from the law, looking to restore his lost honour. He learns that the outlaw couple Jack and Jill have the magic beans he's been looking for most of his life, beans that can lead him to a giant's castle holding valuable golden goose eggs. When Puss tries to steal them from the outlaws' room, female cat Kitty Softpaws interrupts, and both fail. Kitty is allied with Humpty Alexander Dumpty, a talking egg and Puss' long-estranged childhood friend from the orphanage where he was raised. Puss tells Kitty his origin story and of his feelings of betrayal for a youthful misadventure when Humpty tricked Puss into helping commit a bank robbery; Puss has been on the run since. Humpty convinces Puss to join them in finding the beans and retrieving the golden eggs.
The trio steal the beans from Jack and Jill and plant them in the desert. Puss and Kitty's relationship becomes romantic. The trio ride the beanstalk into the clouds to find the castle of the late giant, while avoiding the Great Terror who guards the Golden Goose. When they realize the golden eggs are too heavy to carry, they steal the Goose, which is just a gosling, and escape the castle. While celebrating their victory, the group is ambushed by Jack and Jill, who knock Puss unconscious.
When Puss wakes up, he tracks Jack and Jill to his old hometown where he learns the entire heist was a plot by Humpty to lure him home to be captured, as revenge for abandoning him to the authorities when Humpty's youthful heist went bad. Jack, Jill, and Kitty were involved in the con. After pleas from his adoptive mother, Puss turns himself in to the guards while Humpty donates many golden eggs to the town and becomes a hero.
While in prison, Puss meets the original Jack from "Jack and the Beanstalk" who warns him that the Great Terror is in fact the Goose's mother, and it will stop at nothing to get its child back. A repentant Kitty helps Puss break out of prison and tells him she loves him. Puss tracks down Humpty, who wants the Great Terror to demolish the town. Puss convinces Humpty to help him fight off the Great Terror, saying he knows Humpty is a good person at heart. The Great Terror, a giant goose, arrives. Using the Goose as bait, Puss and Humpty lure the Great Terror out of the town, but Humpty and the Goose are knocked off a bridge with Puss holding onto them. Humpty knows Puss cannot hold both of them, so he lets go, sacrificing himself to save the Goose and the town. Humpty's shell cracks open to reveal he was a golden egg on the inside. The Great Terror then takes the Goose and Humpty back to the giant's castle.
Puss' efforts to save the town make him a hero among the townspeople. In the epilogue, Jack and Jill are recovering from their injuries after being crushed by the Great Terror, Humpty is shown once again in his regular egg form, wearing a golden egg suit, as he rides the Great Terror into the clouds, and Puss and Kitty finally kiss.