At the Central Park Zoo, Marty the zebra is celebrating his tenth birthday, but longs to see the rest of the world from outside his pampered life at the zoo, believing that he can find wide-open spaces to run around in, like Connecticut. Marty's best friend, Alex the lion attempts to cheer up his friend by singing Frank Sinatra's "New York, New York" with him. Still unsatisfied, Marty gets some tips from the zoo's penguins; Skipper, Kowalski, Rico and Private. The penguins are similarly trying to escape the zoo. Marty's friends—Alex the lion, Melman the giraffe and Gloria the hippopotamus—realize Marty's folly and try to follow him. The four, along with the penguins and the chimpanzees Mason and his silent friend Phil eventually find themselves at Grand Central Station, but are quickly sedated by tranquilizer darts when Alex's attempt to communicate with humans is mistaken for aggression. The zoo (under pressure from animal-rights activists) is forced to ship the animals, by sea, to a Kenyan wildlife preserve. During their travels, the penguins escape from their enclosure and take over the ship, intent on taking it to Antarctica. Their antics on the bridge cause the crates containing Alex, Marty, Melmen, and Gloria to fall off the boat and wash ashore on Madagascar.
The animals are soon able to regroup, initially believing themselves to be in the zoo at San Diego, California. Upon exploring, however, they come across a pack of lemurs led by King Julien XIII, and quickly learn of their true location. Alex blames Marty for their predicament and attempts to signal for help to get back to civilization. Marty, on the other hand, finds the wild to be exactly what he was looking for, with Gloria and Melman soon joining him in enjoying the island. Alex eventually comes around, though his hunting instincts begin to show; he has been away from the pampered zoo life of prepacked steaks for too long. The group is accepted by the lemurs, though King Julien's adviser, Maurice, cautions them about Alex's predatory nature. King Julien ignores Maurice's concerns and persuades the group to help the lemurs fend off the fossa, who hunt the lemurs as prey. While initially Alex scares the fossa away and is worshiped by the lemurs, he later enters a feeding frenzy under his starvation and attacks Marty. Realizing that Alex is now a threat to them, King Julien banishes Alex to the far side of the island, where the fossa live. Marty begins to regret his decision to leave the zoo, seeing what Alex has turned into, and realizing how hard it is to survive with so many predators around the island.
The penguins, having been to Antarctica and found that it "sucks", land the boat on Madagascar. Seeing this as a chance to return Alex to New York, Marty rushes after his friend against the wishes of the others. Marty attempts to convince the now grizzled, starving Alex to return, but Alex refuses in fear of attacking him again, despite Marty using the "New York, New York" song. The penguins, Gloria and Melman go to find Marty, but are trapped by the fossa. At the last minute, Alex finally overcomes his predatory nature and scares the fossa away from the lemur territory forever. The lemurs regain their respect for Alex and the penguins help him satisfy his hunger through sushi instead of steak. As the lemurs throw a bon voyage celebration for the foursome, the penguins decide not to break the news that the ship has run out of fuel, and that they are still stuck on the island.