While investigating the sudden appearance of magical portals, Haruto Soma and Koyomi find themselves attacked by Geki Jumonji who attempts to kill the wizard on the notion that his magic poses a threat to universal peace. However, seeing Kamen Rider Wizard risk his life to protect Koyomi and a child from their fight's collateral damage, Space Sheriff Gavan sees the magician to be protector like himself and takes his leave. Returning to the Galactic Union to report to his superior and the previous/original Gavan, Retsu Ichijouji that Haruto is not their enemy, Geki refuses to carry out the mission to eliminate Kamen Riders Wizard and Beast. In response, Retsu relieves Geki from duty and gives the mission to Kai, Space Sheriff Sharivan, with Geki unable to convince his senior to let him investigate further. Elsewhere, with her Go-Buster teammates unable to meet up with them at the campsite, Yoko Usami and her Buddyloid Usada Lettuce notice a strange object crash landing nearby. The two manage to reach the impact site and find a small robot that Yoko brings to the Energy Management Center. Deciding to repair the robot herself, learning he has no memory of his past, Yoko becomes friends with the robot after introducing himself as Psycholon. The next day, ambushed by Kamen Rider monsters, Yoko regains her ability to become Yellow Buster while her teammates are sucked into a magical portal meant for her and Psycholon.
Meahwhile, at the location where Yoko found Psycholon, Haruto battles Shocker grunts before encountering Space Ikadevil of the revived Space Shocker who is looking for Psycholon. Sent through a portal, Kamen Rider Wizard meets the Kyoryugers when they mistook him for a Debo Monster. Impressed, Daigo challenges Haruto to a duel before the Gokaigers' Gai Ikari arrives to halt the match to explain that Space Shocker is behind the portals. With Gai explaining who Geki is, Haruto learns that the Space Galactic Union believe that he and Kosuke Nito are the source of the chaos. Overhearing the story, Kosuke Nito points out Sharivan as he arrives to their location. To dissuade his fellow Space Sheriff as he attacks Gokai Silver and the Kamen Riders, Geki tries to don his Type-G Combat Suit but learns he been locked out of the Dolgiran's systems. After Geki tells him to find the real criminal behind, Haruto uses Space Shocker troops to distract Sharivan long enough for him and the others to hide out. When the Space Shocker troops fall back, Geki follows them as Sharivan sees the Genmu Fortress. On the other side, Geki learns that Space Shocker's magic is provided by Strategist Raider of the fallen Space Crime Syndicate Madou who plans to bring the Genmu Fortress to Earth and consume reality into the Genmu World once they obtain Psycholon. With Gai coming to help him return to their dimension after a brush in with the Kyodain, Geki rescues Yoko and Psycholon from Space Shocker troops with help from Beast.
Taking refuge at the Antique Shop Omokagedō with the others, Gai reveals the existence of Mado to present company with Geki seeing that the only recourse for the Galactic Union to save the universe is to wipe out Earth with the Super Dimensional Cannon. But with Gai telling him that such an option is unacceptable, Geki leaves to meet with Kai who tells him that they are too late to stop Mado from bringing the fortress to Earth and that the Galactic Union will soon destroy the planet. However, as a citizen of Earth, Geki refuses to leave and convinces Kai to give him an hour to stop the Mado/Space Shocker team up while seeing that Gai and Yoko overheard him. As Gai runs off to get reinforcements, Geki leads a group composing of himself, Yoko, Psycholon, and Nito into Genmu World. Kamen Rider Beast holds off Space Kumo Otoko before the Livemen, the Gingamen, the Gekirangers, and Kamen Riders Amazon and Hibiki arrive to offer a helping hand. However, Geki is separated from Yoko when he is grabbed by Space Ikadevil. Luckily, as Gai got her to the Dolgiran, the Shinkengers' Kotoha Hanaori unlocks the transformation system so Geki to transform into Gavan type-G while getting support from Kamen Riders Fouze and Meteor with the Flashmen, the Dekarangers and Kamen Riders Decade and Super-1. Saved by Inazuman/Sanagiman, unaware that their future teacher-student relationship, Fourze defeats Space Kumo Otoko while Gavan and Gokai Silver, attempting to avenge the Kyodain when they return the favor, receive aid from the Gokaigers who use Metal Hero Keys to defeat Space Ika Devil.
At that time, once at the Genmu Castle where her friends are held captive, Yellow Buster finds herself facing Reider and Shadow Moon before Psycholon teleports her friends out of their cell to help her fight Shadow Moon as Gavan, Kamen Rider Beast and the Gokaigers arrive. Fortunately, Kamen Rider Wizard arrives in time to dispel the Genmu Space as the Kyoryugers, Star Sheriffs Sharivan and Shaider, and Kamen Riders Fourze, Meteor and OOO deal with Space Shocker reinforcements. As Shadow Moon is defeated by the Kyoryugers, the heroes gather around Reider before he is mortally wounded by a Dragon Breath/Kentrospiker combo. Learning of that a regretful Retsu fire the Super Dimensional Cannon, Reider reveals in his dying breath that the blast will serve to revive Mado's leader Demon King Psycho. Refusing to allow it, Gavan sacrificed by using the Dolgiran to negate the blast as Sharivan and Shaider join in with the Grand Birth and Vavilos. However, the shockwave provides the energy needed as Psychlone flies off into the core of the Genmu Castle, revealed to be Psycho's actual body. With Reider revived in a new form and an army of Super Sentai monters, Space Reider reveals Psycholne as a part of Psycho. The heroes find themselves in a pinch against their enemies until Akaranger and Kamen Rider 1 arrive with reinforcements that wipe out the Super Sentai monsters, with Kamen Rider Beast defeats Space Reider with aid from Kyoryu Gold and a little bit interruption of a now de-powered Beet J Stag for short. As Wizard joins the Kyoryugers in fight Psycho within Kyoryuzin, Yellow Buster uses the RH-03 to reach Psycholon as it breaks free from Psycho's control and sacrifices itself to protect Yoko. With the Space Sheriffs, who revealed to be alive, using their ships' Big Grand Fire attack to keep him from leaving Earth, Psycho is destroyed by Kyoryuzin equipping WizardDragon for a Zyudenryu Brave Strike End. As the superheroes go their separate ways, Yoko is assured by Usada that they can fix Psycholon while the Geki entrusts Gai with looking over Earth as he now has a new understanding of universal peace before he and the other Space Sheriffs return to space.
To promote the movie, Toei released a series of Internet clips under the collective title Kamen Rider × Super Sentai × Space Sheriff: Super Hero Taisen Otsu: Heroo! Answers(ネット版 仮面ライダー× スーパー戦隊×宇宙刑事 スーパーヒーロー大戦乙(おつ) ～Heroo!知恵袋～,Nettoban Kamen Raidā × Sūpā Sentai × Uchū Keiji: Supā Hīrō Taisen Otsu ~Hīrō! Chiebukuro~?). The net movies also featured characters from Tsuburaya Productions and Marvel Comics. Toei Tokusatsu BB and TV Asahi began distribution on April 12, 2013.