The setting for the story is an ant colony in Central Park in New York City. The protagonist is Z-4195 (Woody Allen), or "Z" for short, a neurotic and pessimistic 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.
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 is unaware that the army's leader and Bala's fiancĂŠ General Mandible (Gene Hackman) is secretly sending all the soldiers loyal to the Queen Ant (Anne Bancroft) 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 is actually marching into battle, and all of the soldiers except for Z are killed by 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 is also congratulated by the secretly irate General Mandible, and is brought before the Queen Ant. There he meets Bala, who eventually recognizes him as a worker. When Z finds that he has been cornered, he panics and pretends to take Bala hostage to trick the queen's guards into letting him leave rather than imprison him. They then escape from a magnifying glass and hide. Z begins searching for Insectopia, a legendary insect paradise that a drunken bar patron named Grebs (John Mahoney) told him about. After an argument, Bala nearly tries to return to the colony on her own, but quickly rejoins Z after an encounter with a praying mantis.
Word of the incident immediately spreads through the colony and Z's act of individuality sparks a revolution in the workers and a few soldier ants as well, grinding productivity to a halt. Seeing an opportunity to gain control, General Mandible publicly portrays Z as a war criminal who only cares 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. However, Colonel Cutter (Christopher Walken), Mandible's second-in-command, slowly begins to have second thoughts about Mandible's plans and develops sympathy for the worker ants.
After some misdirection, Z and Princess Bala stop by a picnic blanket, where they meet two wasps, Chip (Dan Aykroyd) and Muffy (Jane Curtin). The human owning the picnic swats Muffy, and Z and Bala end up on a dramatic ride on the human's Reebok shoes. Finally, Z and Bala find Insectopia, which consists of a human waste-bin overfilled with decaying food. Bala begins to reciprocate Z's feelings.
After interrogating Weaver, Mandible learns that Z is looking for Insectopia. Knowing of the place's existence, Mandible sends Cutter to retrieve the Princess and possibly kill Z. Later that night, Z gathers more stuff to burn at the fire as Cutter arrives in Insectopia. After asking for where Bala is from the inhabitants, Cutter forcefully flies Bala back to the colony against her will. Z finds them gone and makes his way to rescue Bala, aided by Chip, who has made himself drunk grieving over the loss of Muffy.
Z arrives at the colony where he finds that Bala is being 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 Ant 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 prevent 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, but Z pushes Cutter out of the way at the last minute and is tackled into the flooded colony with Mandible. Mandible is killed when he lands upon a root while Z falls into the water. Taking charge, Cutter orders the other soldier ants to help the workers and the Queen Ant onto the surface while he himself rescues Z from the water.
Although it seems that Z is dead, Bala successfully resuscitates him. Z is lauded for his heroism and marries Bala. Together they rebuild the colony, transforming the colony from a conformist military state into a community that values each and every one of its members.

Question: What is Z searching for?
Answer: Insectopia