Newsreel footage shows Godzilla advancing through Tokyo. Created by an H-bomb test and first appearing in Oshiro, the monster tramples the Japanese capital in 1954. The giant dinosaur leaves the devastated city burning in his wake as he lumbers back into the sea, undefeated and unstoppable.

The capital is moved to Osaka even as Tokyo's rebuilding is under way. A second news report from 1966 shows Godzilla's return, attacking Japan's first nuclear power plant at Tokaimura. After his attack, the Prime Minister declares a ban on nuclear energy forever. Alternate forms of energy are hastily developed.

Osaka, 1996. The Bureau of Science and Technology develops a new facility to create 'Green Energy', environmentally friendly plasma power. However, Godzilla is drawn to this energy and soon attacks. Squads of JSDF commandos prepare to try and fend off Godzilla with high-powered rocket launchers. The commandos' efforts are futile, however, Godzilla is far too powerful and he stalks his adversaries through the streets of Osaka, devastating the capital as he exterminates the soldiers. Outside the Bureau, Trooper Kiriko Tsujimori waits for Godzilla, determined to at least slow him down. As Godzilla attacks the plant, she is almost buried under rubble, but her commanding officer, Instructor Miyazawa, pushes her to safety, perishing in her place. Furious, Kiriko fires her rocket at the still advancing Godzilla.

Tokyo, 2001. Kiriko Tsujimori and Sgt Okumura visit the electronics shop of Hajime Kudo, who is amazing some children with little magic tricks. Kiriko reveals the tricks as being accomplished with small micro-machine robots. Disappointed, the children leave. Kiriko reveals that she has come to recruit the electronics whiz. The two soldiers take Kudo to a JSDF base, Camp Shibamura. There, they lead him through a series of check points to a hidden facility. A special G Headquarters has been established to defeat Godzilla. The special agency has departments that track Godzilla, study him and try to develop efective evacuation procedures should he attack again. There is also a combat division - G-Grasper, charged with battling the monster. Kiriko is a part of the G-Grasper unit. Kudo is introduced to the rest of the unit, Lt Hisoi who pilots the combat craft, Sgt Iwai who operates onboard systems, Mr Niikura who handles public relations, and Sgt Okumura, who monitors sonar back in the headquarters. Kudo is surprised to find his old teacher Dr. Yoshino Yoshizawa is also a part of the team. It is Yoshizawa who wants Kudo on the team. Kudo is reluctant, Yoshizawa's last colleagues died in Godzilla's attack on the plasma energy plant in Osaka, although she survived. To prevent a repeat of the Osaka incident, Yoshizawa is developing the ultimate anti-Godzilla weapon. Kudo is intrigued by Yoshizawa's plan to develop a micro-black hole projector which will absorb and erase Godzilla completely, and agrees to join up.

The micro-black hole projector is almost ready for testing and if it works, Kudo's role will be to help miniaturize the device in order that it may be placed into a satellite. The plan is to fire the weapon at Godzilla from space, thereby minimizing the collateral damage caused by the weapon.

At the same time, Godzilla is spotted by GHQ satellites in shallow waters in the Japan Trench. It is not known if he is heading toward Japan and he submerges again almost at once.

Three months pass. Little Jun Kouchi, a boy with a scientific inkling, huries off to school. On his way, he notices a road block closing the country road. Curious as to why soldiers are there, Jun heads into the forest beside the road. He watches from the woods as the JSDF and G-Grasper team prepare to test the black hole gun on an abandoned building. At the test site, Dr. Yoshizawa makes GHQ chief Secretary Sugiura promise that after using the weapon on Godzilla, the device and all the plans for its construction will be destroyed. Sugiura smugly reassures her that it will be done.

Dr Yoshizawa fires the huge cannon and a swirling globe of energy hurtles at the target, sucking air, dirt and building into it, leaving a trench and a crater behind. It also leaves a scatter hole, a rippling field where time and space have been temporarily distorted by the dissipating black hole.

After the test, a sentry summons Kiriko to the woods where the soldier has discovered Jun. Kiriko talks to the boy, making him promise not to tell anyone about what he saw. Exacting the promise, Kiriko lets the boy go.

That night, Jun is unable to sleep, still excited by the day's events. As he lies in bed, something huge flies over the house. Jun hurries outside into the night to try and figure out what it was. His tracks lead him back to the test site where he sees a huge dragonfly creature disappear into the scatter hole left by the black hole gun's discharge. He also finds a strange object, a huge egg with many ugly round bumps.

Jun's family moves to Tokyo and the boy brings his strange find with him. The egg has begun to smell and the boy takes it down to the street to get rid of it. He drops it into the sewer and the object is carried away by the filthy water. Back at GHQ, Kudo tries to flirt with Kiriko, giving her a bullet with a micro transmitter inside, so that if she is ever in trouble she can fire it and Kudo will be able to come and save her. In order to stop Okumura talking to Kudo about their late commander, Instructor Miyazawa, Kiriko asks to test the bullet, firing the transmitter into an exercise weight.

Beneath the streets of Tokyo, the small bumps on the egg break off, floating away in the water. Elsewhere, work proceeds on the satellite as the weapon is reduced in size.

The streets of Tokyo begin to flood as water mains burst. In the entertainment district, a young couple enjoys the night. They stop at a construction site to be alone. They are not, however. Dropping down from the side of a building, a huge insect the size of a horse, a Meganuron, attacks them, killing and devouring them both. Having fed, the Meganuron climbs back up the building. Its skin splits open and the insect emerges from the husk, now a winged Meganura. The winged monster takes to the night sky, frightening Jun as he watches it from the window of his family's apartment.

Guessing what the creature is, Jun contacts Kiriko. Kiriko says it is G-Grasper's fault and responsibility that the creatures are here. She repeats her late instructor's words to tell Jun not to be afraid. Jun shows her the insect in a book of prehistoric animals.

At GHQ, satellites pick up Godzilla, and also the discharge of his heat ray. Analyzing the image, it is discovered that Godzilla was firing his beam at a Meganura.

The G-Grasper unit mobilizes, boarding the advanced fighter craft Griffon. The Griffon soon flies to the spot in the Pacific where the satellite spotted Godzilla. Hovering in mid-air, the Griffon lowers a raft and Kiriko and Imai down to the water. They find the charred husk of the Meganura. But as they examine the carcass, an alert is given. Godzilla is coming back. The raft is thrown back as Godzilla surges upward. Imai is hastily lifted back to the Griffon, but Kiriko remains behind.

Putting on her breath mask and sealing her suit, Kiriko watches as Godzilla surfaces right beside her. She swims to the slow-moving reptile, climbing one of his dorsal spines. She hastily fires one of Kudo's bullets into the monster before her radiation exposure can rise to lethal levels. The Griffon flies down to draw Godzilla away. The Griffon drops a small robot submersible to follow the transmitter, the SGS.

The final instalation of the Dimension Tide weapon in the satellite is made by Kudo. At Japan's space facility, a rocket carries the satellite into orbit. The Dimension Tide deploys, waiting for its moment to attack.

The carcass samples are examined and found to indeed belong to the Meganura species from 35 million years ago. Worse, these things were aggressive and moved in swarms. The lecture is hastily interrupted. The Shibuya district has flooded, most likely due to the Meganurons destroying the water mains. Kudo offers a miniaturized SGS to help search the flooded district. As Shibuya is evacuated, the JSDF begins its search by boat.

Godzilla is discovered swimming toward Chijima. It is decided that Godzilla must be lured to an uninhabited area in order that the Dimension Tide may be used against him. It is decided to force Godzilla onto Kiganjima Island and there destroy him.

Back at GHQ, Kudo installs his home-crafted computer into his work station, claiming that only its operating system will be able to control the Dimension Tide. An animated icon of a nurse double checks that the weapon's programs are okay.

Secretary Sugiura and Kiriko return from parliament with the approval to use Dimension Tide on Godzilla. Dr Yoshizawa protests, insisting that they must test the device in space first. Kudo backs her, saying it still needs adjustments.

The plan proceeds. JSDF fighters drop torpedoes to force Godzilla to the surface. The Griffon arrives to engage the monster, drawing him after the ship and to the island.

At the same time, back in Tokyo, hundreds of Meganuron are found clinging to the side of a building above the flooded streets. As soldiers watch, the Meganurons metamorphose into Meganura and the entire swarm flies away.

The Dimension Tide is placed on standby as Godzilla steps onto the island. As Godzilla enters position, however, the Griffon is rocked from behind by the sudden appearance of the Meganura swarm. The dragonflies at once attack Godzilla. At the same time, the fast moving swarm is fouling up the sensitive targeting systems of the Dimension Tide, making it unable to fire.

Godzilla's heat ray blasts dozens of Meganura from the sky. The Meganura land on the monster, sinking their stingers in him, trying to feed on his energy. Godzilla smashes them with his tail, or against the side of the nearby cliffs. Finally, with a tremendous blast of flame, Godzilla slaughters most of the swarm. With the Meganura decimated, the Dimension Tide is able to fire.

The Dimension Tide sends its deadly energy hurtling down at Godzilla. A blinding light obscures the monster as the black hole absorbs everything. As the dust clears, surviving Meganura fly off and the Griffon moves in. Suddenly, a pile of rubble heaves upward and Godzilla emerges. The weapon has failed to hit him. It will take an hour before the Dimension Tide cools off enough to fire again. Godzilla watches that last Meganura fly off, then glances at the Griffon before lumbering back into the sea.

Sugiura talks on the phone with the Prime Minister, saying that Godzilla is heading for Tokyo and that his target will likely be the National Science and Technology Laboratory. Although he has had the project there stopped, Godzilla may still be coming. Sugiura hastily assures his superior that Godzilla won't effect what they are doing. The line goes dead as the PM hangs up and Sugiura angrily swats the chessmen from his desk in a fit of rage.

The Meganura return to Tokyo, diving into the flooded streets. The dragonflies head for a massive pupa and sink their stingers into it, transferring the energy they stole from Godzilla to the pupa, dying as they do so. The pupa mutates into a giant dragonfly creature.

Kiriko blames Kudo for the Dimension Tide's failure. Dr Yoshizawa breaks up the resulting melee before Kudo can get hurt. She ensures that the weapon will work the next time. Sugiura orders that Godzilla be looked for somewhere between Kigajima Island and Tokyo, claiming that he is just assuming a worst case scenario.

In Tokyo, Kudo meets defense forces at the edge of the flooded district, presenting them with another robot drone to search the water, while he examines the broken one. He learns that many devices and even radios have been breaking down in the area. Kudo wonders if something might be giving off strong magnetic waves underwater.

Beneath the water, the giant dragonfly emerges from its pupa and breaks the surface, hovering in the air. Megaguirus flies off, her vibrating, sharp-edged wings cutting through the side of a skyscraper, destroying the building. Circling at great speed, she causes further destruction by generating devastating sonic booms. Perching on a tower, Megaguirus begins to beat her wings at great speed. She generates a powerful sonic wave that causes Kudo and the JSDF soldiers to reel in pain. As she flies off, a wave of destruction follows her, causing buildings to explode. The JSDF tries to evacuate, but they cannot outrun Megaguirus and the shock wave she is generating. Kudo is injured by falling debris, awakening in an infirmary at GHQ.

It is explained that Megaguirus is a sort of boss or champion of the Meganura species, driving out all threats to the species. The Meganura choose one of their swarm and transfer energy to it to enlarge and strengthen it. There have been fossils of these creatures found in China.

Godzilla is indeed found to be heading for Tokyo. The city is quickly evacuated in anticipation of Godzilla's arrival. Jun and his mother are among the evacuees.

Back at GHQ, Kiriko wonders what is in Tokyo that it is drawing Godzilla. In 1966 and 1996, he was drawn by power plants, but there are no such facilities in Tokyo now. Dr Yoshizawa wonders if this is true. Before this line of thinking can be pursued, the exact point of Godzilla's landing is determined. G-Grasper scrambles to the Griffon.

The Griffon arrives at Tokyo Bay just as Godzilla appears. The craft engages Godzilla, avoiding his heat ray and firing plasma missiles at him. Once again, however, the battle is interrupted. Megaguirus appears, flying over the Griffon toward Godzilla.

Megaguirus and Godzilla face off for a moment, then the insect monster dives to the attack, slashing Godzilla with her wings. Megaguirus continues to attack Godzilla with hit-and-run assaults, often from behind.

In GHQ, Sugiura orders the Dimension Tide readied, hoping to eradicate both monsters at once.

The battle continues, but Megaguirus is too nimble and quick for Godzilla's ray to hit her. The insect batters Godzilla with her shock wave, also causing a magnetic disturbance that causes the Dimension Tide relay to lock up, preventing it from firing. Megaguirus continues to stalk and strike Godzilla while dodging his ray. The dragonfly grapples with Godzilla, while the Griffon makes a forced landing atop a building, the electronics on the craft seizing up after Megaguirus' high frequency attack.

Megaguirus stings Godzilla, draining his energy, even preventing him from firing his ray. The insect drags the weakened reptile away, slamming him into a building, then circles back to collapse the structure on him. Wounded and furious, Godzilla emerges from the rubble.

Megaguirus hurtles forward to attack again, but as the dragonfly dives at him, Godzilla bends down, allowing the insect to strike his dorsal plates. Megaguirus flies off, one of her claws falling away, severed by the high-velocity impact with Godzilla's spines. The angry insect tries to attack Godzilla from behind but the reptile's tail wraps around her own and whips Megaguirus around, hurling her into the remains of the building she collapsed onto Godzilla. Megaguirus rises from the ruins.

Back at GHQ. Kudo rises from his sick bed and enters the control room, determined to fix Dimension Tide, using an updated system that features an icon in the shape of Kiriko.

The battle proceeds, both monsters grappling once more. Godzilla leaps into Megaguirus, but the insect soon escapes once more before he can deal any serious damage. Megaguirus uses the energy she has taken from Godzilla to generate a massive plasma ball with her wings. The blast stops the charging Godzilla in his tracks, dropping him. Megaguirus swoops in, battering Godzilla with her tail. As she dives in for the kill, however, Godzilla bites her tail, destroying her stinger. The maimed dragonfly is stunned. Godzilla at last succeeds in hitting the insect with his heat ray and Megaguirus explodes, her burning carcass dropping to the earth enveloped in flame. Godzilla roar in triumph and proceeds into Tokyo.

At the same time the Dimension Tide's orbit begins to decay and the weapon starts to fall back to earth. Kudo tries to fix it. Sugiura leaves by helicopter, Dr Yoshizawa wonders what he is hiding and insists on going with him.

The Griffon is hastily repaired, though its weapon system is not working, and the craft streaks off to pursue Godzilla.

Godzilla closes on the laboratory, destroying it. Sugiura and Dr Yoshizawa watch from a rooftop, soon joined by the Griffon and the G-Grasper crew. Sugiura has been hiding the fact that the lab was trying to develop plasma energy again, that is what drew Godzilla back to Tokyo. Plasma energy is necessary to lead Japan to greater profit and growth, hence the conspiracy to continue researching it, even after Godzilla's attack in 1996. An enraged Kiriko strikes the bureaucrat after he says that all the lives lost by Godzilla's attack were necessary.

Kudo gets the Dimension Tide weapon operable, though it is still falling. He contacts Kiriko, telling her that they are going to try and fire on Godzilla. As the satellite enters the atmosphere, the targeting system fails. Kiriko takes the Griffon without the crew and flies toward Godzilla. She hopes to get the Dimension Tide to lock onto the Griffon, then lead the micro-black hole straight into the monster. She gets the weapon to lock-on the Griffon, then flies back into Tokyo. She dives the Griffon into Godzilla, ejecting before it hits, and Kudo fires the Dimension Tide seconds before the weapon explodes.

The black hole plummets downward. Godzilla fires his beam at it, momentarily stopping it. But the black hole still descends and Godzilla is lost to view as the black hole sucks everything into itself. When the discharge clears, Godzilla is gone, only a crater and rubble left behind.

With Godzilla gone, Kudo returns to his shop, listening to a news report about the Prime Minister and Secretary Sugiura being called before the Parliament inquiry into the plasma energy being developed in Tokyo despite the ban. Kiriko arrives. There has been an earthquake under Tokyo. She wonders if Godzilla possibly wasn't absorbed by the Dimension Tide. She wants Kudo to help them again.

At school, Jun is frightened by another earth tremor. As he takes cover, the sound of Godzilla's roar fills the air.