The movie opens with Buzz Lightyear infiltrating the Evil Emperor Zurg's fortress before getting vaporized by Zurg himself. This is revealed to be a video game that Rex is playing, being unable to defeat Zurg. Several years after the first movie, Woody and Buzz Lightyear are now the co-leaders of Andy's toys. Woody searches for his lost hat, which Slinky gives to him as it was taken by Buster, the pet dog Andy got at the end of the first movie.
Andy is preparing to take Woody to cowboy camp, but while playing with Woody, Buzz and all the other toys, Andy accidentally tears Woody's arm, leaving him unable to bring Woody to camp. Andy's mother places Woody on the shelf. Woody has a nightmare about Andy throwing him away before discovering Wheezy, a toy penguin who has been left on the shelf after his squeaker broke.
Woody sees Andy's mom putting up a yard sale sign outside. He tells the other toys to have an emergency roll call. Before they can finish, Andy's mom comes in and takes a handful of items, including Wheezy. Woody calls Buster and rides on him to get to the yard sale to save Wheezy. Woody manages to rescue him but falls off of Buster. He gets spotted by Al McWhiggin, a toy store owner. He tries to buy Woody, but when Andy's mom says he isn't for sale, Al steals him. Buzz manages to get to Al's car as he's driving away, but by the time he opens the trunk, Buzz loses his grip from the car as it escapes. However, the feather from a chicken suit and the license plate LZTYBRN help Buzz deduce who Woody's kidnapper is. He sets out to rescue Woody with the help of Rex, Hamm, Slinky and Mr. Potato Head.
Woody is taken to Al's apartment, where he is greeted by a yodeling cowgirl named Jessie, a horse named Bullseye, and a prospector named Stinky Pete, an unsold toy still in its original box. They tell Woody that he's a vintage collector's item doll and he had a children's TV show titled Woody's Roundup in the 1950s. Now that Al has a Woody doll, he has a complete collection and intends to sell the toys to a museum in Japan. Woody refuses to go to Japan and abandon Andy, which causes Jessie to resent him as she does not want to go back into storage.
Al is about to take photos of the four toys, but accidentally rips Woody's arm off. Woody tries to retrieve it and escape while Al is sleeping, but his attempt fails when Al's television unexpectedly turns on. Woody blames Jesse since the TV remote was in front of her case. Al has a repairman fix Woody's arm, as well as cover up Andy's name on the bottom of his boot. Jessie tells Woody about her previous owner Emily, who eventually outgrew her and donated her at a charity toy drive. Stinky Pete warns Woody that Andy will do the same one day, and that he has the choice to be enjoyed by children forever. Woody ultimately decides to stay and go with the other toys to Japan.
Buzz and the other toys reach Al's Toy Barn after crossing a busy street by hiding themselves inside traffic cones. The toys split up to look for Al; Buzz comes across an aisle of Buzz Lightyear toys, where he finds Utility Belt Buzz, who thinks he's a real Space Ranger, just like Buzz in the first movie. Utility Belt Buzz imprisons Buzz inside a box. Andy's toys mistake Utility Belt Buzz for their Buzz and discover Al's plans to sell Woody. Andy's Buzz breaks free and follows after Al, who lives in an apartment right across the street from the toy store. As Buzz leaves the store, he accidentally frees a Zurg toy, who follows after him to destroy him.
Andy's toys, as well as Utility Belt Buzz, all make it to Al's apartment, where Buzz proves he's the real Buzz by showing Andy's name on the bottom of his foot. Woody tells the other toys he does not want to be rescued. Buzz tries to persuade Woody to come home, but Woody remains adamant that life in the museum would be better than potential abandonment by Andy. Disheartened, the two Buzzes and Andy's toys leave.
Woody watches the puppet version of himself on TV perform "You've Got a Friend in Me", then looks at Andy's name at the bottom of his boot. He decides that even if he can't stop Andy from growing up, he wouldn't miss it for the world. He calls Buzz to come back before inviting the Roundup gang to come with him and experience playtime from Andy. Jessie is uncertain, but Bullseye agrees. However, the Prospector traps them in the room, revealing that he framed Jessie for turning on the TV to prevent Woody from escaping last night and saying that the museum trip is his first chance since he was never sold and won't have Woody or anyone else mess it up for him.
Al returns and packs the Roundup Gang. The rest of the toys run to the building's elevator, but are interrupted by the sudden appearance of the Emperor Zurg toy. Utility Belt Buzz battles him before Zurg reveals himself to be Buzz's father. Rex accidentally defeats Zurg by knocking him off the elevator with his tail. Utility Belt Buzz and Zurg are now playing father and son games and depart from Andy's toys. Andy's toys chase after Al by driving a Pizza Planet truck containing three Little Green Men toys, who become grateful to Mr. Potato Head for saving their lives after they almost fall out the car's window.
At the airport, the toys search for Al's suitcase. Several of the toys find an identical suitcase containing camera flashes. Buzz finds Al's case, but is punched by Stinky Pete. Outraged, Woody fights the Prospector who then gains the upper hand and tears open Woody's arm using his pickax. Buzz and the other toys use the camera flashes to blind and capture Stinky Pete. They stick him in a little girl's backpack so he can learn the true meaning of playtime. Pete is terrified to learn that the little girl likes to draw on all of her toys before sobbing in despair. Bullseye is freed from the suitcase, but Jessie finds herself in trouble and remains trapped in the suitcase. Woody and Buzz ride Bullseye in order to rescue her from being taken to the museum on her own.
Woody manages to find Jessie, but just when they're about to escape, the door closes and the plane heads for the runway. Woody finds another way out through a small hatch which leads down to the landing gear wheel. Jessie catches Woody as he slips; his rip gets bigger and his hat is flown away. Buzz and Bullseye appear in time to catch the hat. When the plane is at the main runway, Woody tells Buzz to get behind the plane's wheel; he and Jessie swing down to safety on Bullseye's back just seconds before the plane takes off. The toys make it back home before Andy returns.
Andy repairs Woody's arm himself, and paints his name on Jessie and Bullseye's feet. After Hamm fails at the Buzz Lightyear video game, he sees Al in an Al's Toy Barn commercial, sobbing since he lost his luggage. Mrs. Potato Head adopts the three toy aliens, much to Mr. Potato Head's dismay. Wheezy has also had his squeaker fixed and sings "You've Got a Friend in Me." Buzz asks Woody if he's still worried about Andy, to which Woody says that he isn't worried anymore, and that when it is all over, he will have Buzz to keep him company, for infinity and beyond.
