The prologue of the film acknowledges the events of the first Godzilla film (using the present Godzilla monster rather than the 1954 monster), while inventing its own timeline, explaining that the capital of Japan was moved from Tokyo to Osaka. The film takes place in an alternate universe with advanced technology, explaining that in 1966, Godzilla attacks the first Japanese nuclear plant in Tokai, Ibaraki Prefecture. After this, a section of Japanese Self Defence Force was dedicated to fight Godzilla, and was called G-Graspers. In 1996, clean plasma energy replaced nuclear energy, however this did not deter Godzilla from attacking. Plasma energy is also banned, due to the fact that Godzilla attacked the original plasma energy reactor.
In 2001, an experimental satellite-based weapon that fires miniature black holes, called the Dimension Tide, opens a wormhole through which a prehistoric dragonfly enters the present and deposits a single egg before exiting through the wormhole. A boy finds the egg and takes it with him when he moves to Tokyo. The egg starts oozing a strange liquid, so the boy throws the egg in the sewer. The egg, actually a mass of hundreds of eggs, splits up and starts growing when exposed to water, hatching into large dragonfly larva called Meganulon that come out of the sewer to feed. They flood a portion of the city and moult on the sides of buildings, becoming adult Meganula.
Meanwhile, the atomic dinosaur Godzilla appears, in search of a source of nuclear energy, despite the edict shutting down all such attractants after its three previous appearances. While Godzilla is fighting the G-Graspers, who are assisted by rebellious scientist Hajime Kudo, the swarm of Meganula are attracted in turn to Godzilla's energy, and attack it. During the course of the battle, the Dimension tide is launched, but Godzilla survives the attack. Most of the Meganula are killed by both Godzilla and the Dimension Tide, but a few manage to drain off some of Godzilla's energy and return to the sewer. With the last of their strength, the Meganula inject Godzilla's energy into a huge, sleeping larva that is in a giant, pulsating cocoon. It molts and appears from the water as Megaguirus, the queen of the Meganula.
After destroying part of the city with shock waves generated by her beating wings, Megaguirus heads to the waterfront and faces Godzilla. Being territorial, Megaguirus considers the city to be her hunting ground. As they engage in a lengthy battle, she uses her speed to avoid Godzilla's attacks, but Godzilla eventually uses her speed against her. As she flies toward Godzilla, Godzilla lunges forward with its dorsal fins in her path. She flies into the fins, and one of her arms is severed.
During the battle, a special ability of Megaguirus is revealed: Having been mutated by Godzilla's energy, she can generate a blast similar to Godzilla's atomic breath. She fires a huge ball of radiation, knocking Godzilla down. Godzilla gets back up, and Megaguirus goes in for the kill. She speeds forward with the stinger on her long tail lowered, trying to stab Godzilla between the eyes. In a climactic moment, Godzilla catches the stinger in its mouth. Godzilla bites down, crushing the stinger. Megaguirus rears up in pain, and Godzilla takes the chance to finally blast her with atomic breath. Megaguirus bursts into flames and Godzilla blasts her a second time and destroys her.
It is revealed that Godzilla was attracted to the energy of a secret Plasma Energy project housed at the Science Institute, in violation of the ban, by Professor Yoshino Yoshizawa. The G-Graspers continue their mission to destroy Godzilla, but with the Dimension Tide falling out of orbit they are unable to get a lock on Godzilla, until the vengeful Major Kiriko Tsujimori pilots a ship called Gryphon towards Godzilla, ejecting only at the last second. The Dimension Tide is able to lock on to the craft and fires just before burning up on reentry; Godzilla blasts at the approaching black hole with its atomic fire but vanishes and everyone celebrates. In a postlude, however, Major Tsujimori again enlists Kudo to investigate suspicious seismic activity; then in an after-credits scene, Godzilla's roar is heard again at the school room where the boy who originally found the egg is, shakes. An after-effect of the Dimension Tide machine is temporary wormholes. As Megaguirus came to Earth through one, did Godzilla return to Earth through a wormhole caused by it being sent into the black hole?