The story starts right where Gamera 3 ends, with the JSDF rushing to confront the swarm of Gyaos invading Japan. Squadron after squadron, jets dogfight with the Gyaos, only to be mercilessly defeated by the monsters. A wounded Gamera takes off from the burning ruins of Kyoto to join the midair battle, where he spins off wild mana shots that pick off a few Gyaoses. Ganged upon by his malevolent opponents, Gamera's troubles are complicated when the swarm is joined by Albino Gyaos, a larger, souped-up, all-white version of the Hyper-Gyaos. Finally, all take aim and fire their super-sonic beams on Gamera, plunging him to a watery grave.
Following the battle, the Japanese government enlists the help of Nagamine and Osako to help the military search for the new monster. After locating it, the JSDF deploys a large force of tanks, rocket launchers and helicopters, but the A-Gyaos proves too strong for them. Later, the A-Gyaos attacks the hotel Osako is staying at, and he is presumed dead in the rubble. Finally, the military pits a heat ray tank, the SGPM-2, against Gyaos, but it, too, fails miserably.
One of the ancient Gamera skeletons is given mana power from the earth and regenerates into a new Gamera. Landing in Yokohama Bay, Gamera lays waste to everything in sight. A-Gyaos arrives to attack Gamera, and the two engage in a climactic clash. The new Gamera eventually prevails over his arch nemesis, yet does not return to the sea. Instead, he continues on a rampage, stomping and burning everything from Yokohama to Shinjuku. The JSDF launches a last ditch offensive in Shinjuku using heat ray tanks, but Gamera easily thwarts the attack. Suddenly, a huge explosion erupts from Gamera, and central Tokyo is reduced to smoldering ruins.
Soon after the climatic action sequence, Osako is still alive in Okinawa (as far away from Tokyo as possible), wondering how he always manages to survive such calamities. As he hobbles away, a news broadcast is overheard. It turns out that the new Gamera opened a crater one kilometer wide and four hundred meters deep in the center of Tokyo. The Japanese and U.S. military found many unclassified prehistoric eggs deep within the crater, leaving the audience to wonder if this was Gamera's true target.