The premise of King Gainer is that, after an environmental cataclysm, much of the world's population retreated into domed cities called Domepolis, which are run by a organization known as London IMA (International Management Authority) and its police arm, Saint Reagan. However, the Domepoli are maintained and supplied by privatized firms such as Siberia Railroad company.
A group that wishes to breakaway from the control of the railroad companies and the London IMA is Exodus, whose goal is to journey to the vaunted land of Yapan. As the story begins, championship video game player Gainer Sanga is arrested by Siberia Railroad policewoman Adett Kisler on suspicion of being an Exodus member. Ironically, he isn't, but, without his knowledge, his friends Sara Kodoma and Bero Korissh and his schoolteacher Mamato Azav are members of the Gauri team, a local Exodus group. At the same time, Exodus mercenary Gain Bijou lets himself be arrested by the Siberia Railroad police.
In the same prison cell, Gain Bijou and Gainer escape and infiltrate the castle of Duke Medaiyu and steal an Overman, a biomechnical giant robot, which Gainer logs into as his nom de videogame, King Gainer. As Gainer gets the hang of piloting a real Overman, he and Gain encounter shut-in Princess Anna, the Duke's daughter, who wants to see world and other people than her tutor, Rubov Smettana. Using an annual festival presented by idol singer and one of the five Exodus leaders, Miya Raujin, as cover, the Exodus executes their plan: take the much of the Domepolis, block by block, using heavy hauler machines called Silhouette Mammoths and move them over 3000km across the Siberian tundra to Yapan. As the Exodus moves out, the Siberia Railroad police chief, Yassaba Ginn, begins to mobilize his forces to stop them. Other obstacles to the Exodus are Kisler's and Jinn's subordinates Javoli Mariera, Kejinan Daddo, and Inge Gam, Siberian Railroad president Kidz Munto, Saint Reagan policemen Artham Boone and Zakki Bronco, and Overman aces Cynthia Rein and Kashimar Burleigh.
Overman King Gainer was a significant departure from Tomino's usual 'stùrm und drang' proceedings that resulted in his nickname of 'Kill all Tomino'. King Gainer was well received and its unusual opening, which features all the characters and even the Overman themselves performing the dance move known as 'the monkey', has become a fan favorite.