Many days after bidding the penguins goodbye, Alex the lion suggests to his friends, Marty the zebra, Melman the giraffe and Gloria the hippopotamus and the lemurs, King Julien XIII the ring-tailed lemur, Maurice the aye-aye and Mort the mouse lemur that they should go to Monte Carlo to get the penguins and chimpanzees, Mason and Phil and fly back to New York City, which they agree to do.
In Monte Carlo, the penguins and chimpanzees have been saving up their daily winnings from the casino to fly back to Africa and bring their friends home. Alex's interference to kidnap them leads to animal control, led by a vicious big-game hunter named Chantel DuBois, pursuing them around the city, with Alex and the gang barely escaping. With determination, DuBois vows to capture Alex and add his head to her collection of animals' heads she's captured.
In the skies of France, the plane crashes as the authorities close in. They come across a circus train consisting of Stefano the sea lion, Gia the jaguar, and Vitaly the tiger, and manage to gain entry, claiming that they are circus animals themselves. The team soon learn from Stefano that they are performing in Rome and London, where they plan to impress a promoter to get them on their first American tour. Before the zoo animals' claim is discredited, the penguins suddenly appear with a deal to purchase the circus themselves; however, the circus animals' show in Rome proves to be a failure.
In route to London, Stefano soon reveals to Alex that Vitaly was the biggest star of them all, but quit due to an accident in one of his stunts; therefore, the friends lost faith in the circus. At a stop in the Alps, Alex convinces the circus to continue pursuing the circus. Marty finds a new passion in being shot out of a cannon along with Stefano, while Melman and Gloria decide to dance on a tightrope. Gia persuades Alex to teach her Trapeze Americano. In the process, they grow closer.
Meanwhile, DuBois is arrested in Rome while chasing the animals, but escapes and discovers that Alex was the missing lion from the zoo in New York. Once free, DuBois personally reassembles her injured men and they head toward the Alps, forcing the animals to proceed to London despite incomplete rehearsals. Alex finds Vitaly preparing to leave and convinces him to stay by reminding him of how he enjoys performing the impossible. He suggests that he uses hair conditioner as a safer lubricant to perform his flaming ring jump as well as fix his damaged fur. As a result, Vitaly's stunt is performed perfectly and the show is a spectacular success. After the impressed promoter arranges for an American tour, DuBois shows up with a paper showing that Alex was missing. Though the penguins are able to foil Dubois' plan, Alex is forced to confess that the four of them are just zoo animals trying to get home, disappointing the others who feel used and lied to.
The zoo animals and circus go their separate ways but arrive in New York City at the same time. Realizing how much their adventures have changed them, the zoo animals find that their true home was with the circus. Before they can go back, however, DuBois tranquilizes and captures them, before being discovered by the zoo staff, who believe she is responsible for returning the missing animals. King Julien and the penguins manage to get to the circus and convince the circus animals to rescue their friends.
Back at the zoo, Alex awakens to find that he along with his friends are trapped in larger fence enclosures. DuBois, who was honored by the zoo guards, secretly loads a poison-filled dart into a gun that she hides inside a foam finger in preparation for publicly executing Alex. The circus animals arrive led by Skipper and are able to defeat DuBois and her henchmen. Alex and his friends eventually decide to permanently join the circus to pursue their adventures, while DuBois and her henchmen are sent off in crates bound for Madagascar (just like the zoo animals themselves were in the first film) thanks to the penguins.