In 1821, the Mexican Army is on the verge of liberating its country from Spanish colonial rule. In the area of Las Californias the ruthless Spanish Governor, Don Rafael Montero, is about to be overthrown. In a last ditch effort to trap his nemesis, the masked swordsman Zorro (Anthony Hopkins), Montero prepares to execute three innocent townspeople. With assistance from two orphan brothers, Joaquin and Alejandro Murrieta, Zorro releases the prisoners. Zorro rewards the Murrieta brothers with a special medallion he wears, and escapes on his horse, Toronado, after cutting a "Z" into Montero's neck as a parting gift and warning.
The same night, however, Montero confronts Zorro at his home, having deduced that Zorro is really Don Diego de la Vega, a Spanish nobleman married to Esperanza, the woman Montero had always loved. Attempting to arrest Diego, a fight ensues, during which Esperanza is killed while trying to protect Diego. Diego's house is burned and his infant daughter, Elena, is taken to Spain by Montero to be raised as his own while Diego is taken to prison.
Twenty years later, Montero secretly returns to California, looking for Diego in the old prison. Although de La Vega is there, Montero does not recognize him, while several prisoners claim to be Zorro. Diego later escapes, intent on killing Montero the following day at a public ceremony for Montero's return. However, Diego restrains himself when he sees Eléna (Catherine Zeta-Jones), now a beautiful young lady. Elena is presented with a bouquet of flowers - Romneyas, native to California - the scent of which she recognizes, although she incorrectly believes she has never been to California before.
Diego soon meets an adult Alejandro Murrieta (Antonio Banderas), whom he recognizes by the medal he awarded Joaquin. Now a drunken, clumsy bandit, Alejandro is bitter over the recent capture of his mentor, bandit Three-Fingered Jack (L. Q. Jones), and the murder of Joaquin by the sadistic Texian Army Captain Harrison Love, Montero's commander-in-chief. Diego recruits and trains Alejandro to become his successor.
After some training, Alejandro dons a makeshift costume and clumsily steals a black stallion resembling Tornado, Diego's former steed. En route, Alejandro encounters Eléna. Escaping from Captain Love, Alejandro seeks refuge in a nearby church, with the assistance of the town priest and Zorro's old friend, Father Felipe. Alejandro hides in the confessional, where Eléna unwittingly reveals her infatuation with the mysterious "bandit" she had just met.
Upon his return, Diego scolds Alejandro, claiming that Zorro was a servant of the people, not a thief and adventurer. Diego rebuffs a challenge by Alejandro, instructing him that to gain Montero's trust, Alejandro must convince Montero that he is "a gentleman of stature." Posing as visiting nobleman Don Alejandro del Castillo y García, with Diego as his servant, Alejandro attends a party at Montero's hacienda, where he quickly gains Eléna's admiration and enough of Montero's trust for the latter to invite him to a secret meeting. There, Montero hints at a plan to retake all of California for the Dons by buying it from their hero, General Santa Anna, who is desperately in need of money to fund his ongoing war with the United States.
The next day, Alejandro and the Dons are taken by Montero to a secret gold mine known as "El Dorado", where peasants and petty criminals are used as slave labor. Montero reveals that he plans to buy California from Santa Anna using gold mined from his own land. Three-Fingered Jack, now a slave, attacks the noblemen and is killed by Captain Love. Meanwhile, Diego uses this opportunity to become closer to Eléna, though he identifies himself as "Bernardo" the servant (a homage to the name of Zorro's mute sidekick from the original story), learning that Montero told Elena that her mother died in childbirth. Later, while walking in a local market, Eléna meets the woman who had been her nanny and used to hang romneyas on her crib.
Diego later sends Alejandro, dressed as Zorro, to steal the map leading to the gold mine from Montero's hacienda. In the process, Zorro duels and fights off Montero, Captain Love, and their guards. As he escapes to the stable, he is confronted by Eléna, who attempts to retrieve the map belonging to her "father." While Elena shows considerable skill with a sword, Zorro nonetheless manages to defeat her, then playfully cuts off her bodice, leaving her in nothing but her underwear and her long tresses. After a passionate kiss, Zorro flees the stable and shakes off his pursuers. Meanwhile, terrified of Santa Anna's retribution if he discovers that he is being paid with his own gold, Montero and Captain Love decide to destroy the mine with explosives and kill the workers, thereby leaving no evidence.
Alejandro uses the stolen map to locate the mine in order to release the workers. Diego tells Alejandro to release them on his own, so that he can confront Montero and reclaim Elena as his daughter. Alejandro sets off to the mine, feeling betrayed by Diego's personal vendetta. Later that night, Diego corners Montero at the hacienda and reveals his true identity. After being summoned by her presumed "father," Montero captures Diego after threatening to kill him in front of Elena. As he is escorted away by guards, Diego tells Elena the name of the flowers she recognized upon her arrival to California, convincing her that Diego is her true father. She later releases Diego from his cell, and they proceed to the mine.
There, Zorro prevents Captain Love from loading gold onto a wagon to be taken from the mine, and engages him in a duel. Diego prevents Montero from shooting Zorro, and they also duel. After disarming Montero, Eléna appeals for him to spare Montero's life. Montero capitalizes by threatening Eléna, and then wounding Diego. Zorro ultimately defeats and mortally wounds Love in a protracted swordfight taking them through various points around the mine. Though mortally wounded, Diego also defeats Montero, by having a gold-laden wagon drag Montero off a cliff and crushing Love in the process. Eléna and Alejandro, now without his mask, free the captive workers before the explosives set by Love go off.
Before dying in their arms, Diego makes peace with Alejandro, fully passes the mantle of Zorro to him, and gives his blessings for Alejandro's and Elena's prospective marriage. In the film's epilogue, Alejandro and Eléna are married and have a son named Joaquin, in honor of Alejandro's brother. As Elena puts Joaguin to sleep, Alejandro exits the room and as Zorro, draws his sword and makes his trademark 'Z' as the credits roll.
