The setting for the story is an ant colony in Central Park in New York City, over the span of four days. The protagonist is Z-4195 (Woody Allen), or "Z" for short, a neurotic and individualistic worker ant living in a wholly totalitarian society who longs for the opportunity to truly express himself. His friends include fellow worker Azteca (Jennifer Lopez) and a soldier ant, Weaver (Sylvester Stallone). Z meets Princess Bala (Sharon Stone) at a bar where she goes to escape from her suffocating royal life and falls in love with her.
In order to see Bala again, Z exchanges places with Weaver and joins the army. He marches with the ranks, befriending a staff sergeant named Barbatus (Danny Glover) in the process. He doesn't realise that the army's leader and Bala's fiancé, General Mandible (Gene Hackman), is secretly sending all the soldiers loyal to the Queen to die so he can begin to build a colony filled with powerful ants. At the base of a tree near nightfall, Z realizes he's actually marching into battle, and all of the soldiers except for Z are killed by the acid-shooting termites. Following the battle, all Z can find of Barbatus is his head. Before he dies, Barbatus tells Z to think for himself rather than follow orders all his life, leaving Z saddened and depressed. Z returns home and is hailed as a war hero, even though he did not do anything and was traumatized by the fighting. He was also congratulated personally by the secretly irate General Mandible, and is brought before the Queen. There he meets Princess Bala, who eventually recognizes him as a worker. When Z finds that he has been cornered in a lie, he panics and pretends to take Princess Bala "hostage" in order to trick the queen's guards into letting him leave rather than imprison him. They escape the colony and hide, and Z begins searching for the legendary Insectopia.
Word of the incident quickly spreads through the colony, whereupon Z's act of individuality sparks a revolution in the workers and, possibly, a few soldier ants as well. As a result, productivity grinds to a halt. Seeing an opportunity to gain control, General Mandible begins to publicly portray Z as a war criminal who cares only about himself. Mandible then promotes the glory of conformity and promises them a better life, which he claims to be the reward of completing a "Mega Tunnel" planned by himself. Mandible learns Z is looking for Insectopia after interrogating Weaver. Knowing full well of the place's existence, Mandible sends his second-in-command, Colonel Cutter (Christopher Walken), to its location to retrieve the Princess and possibly kill Z. Cutter, however, slowly begins to have second thoughts about Mandible's plans and agenda and develops sympathy for the worker ants.
Z and Bala, after a misdirection and a brief separation, finally found Insectopia, which consists of a human waste-bin overfilled with decaying food (a treat for insects of all kinds). Here, Bala begins to reciprocate Z's feelings. However, during a break, Cutter arrives and flies Bala back to the colony against her will. Z finds them gone and makes his way to rescue Bala, aided by a wasp named Chip (Dan Aykroyd), whom he met earlier and has made himself drunk grieving over the loss of his swatted wife, Muffy (Jane Curtin). Z arrives at the colony, where he finds that Bala has been held captive in General Mandible's office. After rescuing her, he learns that General Mandible's "Mega Tunnel" leads straight to a body of water (the puddle next to Insectopia), which Mandible will use to drown the queen and the workers who have gathered at the opening ceremony. Bala goes to warn the workers and her mother at the ceremony, while Z goes to the tunnel exit to stop the workers from digging any further. He fails, however, and the water leaks in. Z and Bala unify the workers into a single working unit and build a towering ladder of ants towards the surface as the water continues to rise.
Meanwhile, General Mandible and his soldiers are gathered at the surface, where he explains to them his vision of a new colony with none of the "weak elements of the colony". He is interrupted, however, when the workers successfully claw their way to the surface and break through. Mandible angrily tries to kill Z but is stopped by Cutter, who finally rebels against Mandible and instead tries to help Z and the worker ants out of the hole "for the good of the colony." The enraged Mandible charges toward Cutter, who is, however, pushed away by Z at the last moment. Mandible inadvertently takes Z with him back down into the flooded colony, and is killed when he lands upon a root while Z falls into the water. Cutter, taking charge, orders the other soldier ants to help the workers and the queen onto the surface while he himself rescues Z. Although it seems that Z has drowned, Bala successfully resuscitates him. Z is lauded for his heroism and marries Bala. Together they rebuild the colony with Cutter as their General, transforming the colony from a conformist military state into a community that values each and every one of its members.