趣味でヒーローを始めた男、サイタマ。その昔、就職活動をしていたある日、偶然出会った怪人から子供を救ったことをきっかけに小さい頃からの夢であったヒーローを目指した彼は、3年の特訓の後どんな敵をも一撃で倒す無敵の強さを手に入れた。しかし、憧れのヒーローとなり充実した毎日を送っているはずの彼は、その強さ故に常にワンパンチで決着がついてしまう戦いを繰り返すうち、次第に自らの圧倒的な力に対して物足りなさを感じるようになっていた。

獲物の血をミイラ化するまで吸い尽くす凶悪な蚊の大群がZ市に押し寄せた。蚊の群れを操っていたのは「進化の家」という謎の組織によって生み出された怪人モスキート娘。とそこへモスキート娘に立ち向かう一人の男が現れる。彼の名はジェノス。自らの身体を機械に変えて悪と戦う正義のサイボーグだ。モスキート娘との死闘の末に絶体絶命のピンチに陥ったジェノスは、たまたま通りかかったサイタマに命を救われる。数日後、命の恩人であるサイタマの元を突然訪ねたジェノスは彼に弟子入りを志願するのだった。

「進化の家」の刺客を返り討ちにしたサイタマとジェノスは、刺客の一人アーマードゴリラから組織に関する情報を聞き出した。進化の家の創設者であるジーナス博士は人類の人工的進化という危険な思想を掲げており、サイタマの強靭な肉体を研究に利用しようとしていたのだ。彼の企みを阻止するため、二人はその足で敵の本拠地へと向かう。一方、アーマードゴリラの通信によってそれを知ったジーナス博士は、二人を迎え撃つために進化の家の最終兵器を解き放とうとしていた。それは凶暴すぎるあまりにジーナス自身でさえコントロール不能な史上最凶の悪魔、阿修羅カブトだった。

桃源団を名乗るテロリストの一団がF市に現れた。構成員全員がスキンヘッドという異形の一団を率いるのは、バトルスーツに身を包んだ大男ハンマーヘッド。彼は「断固働きたくない」という自らの思想に共鳴する若者たちと共に、働かない者は働きたい者に養ってもらえる理想郷の実現を目指していた。まずは見せしめとして町一番の富豪であるゼニールの豪邸を破壊しようとする桃源団。そんな彼らの前にゼニールに雇われた用心棒の忍者、音速のソニックが立ち塞がる。一方、桃源団の存在をニュースで知り、髪型がかぶっているせいで自分もその一味だと思われることを危惧したサイタマも、桃源団を潰すために彼らの元へと向かっていた。

趣味でヒーローを始めて3年。自らの知名度の低さを思い知らされたサイタマは、プロのヒーローとして公式に活動していく決心をする。ジェノスと共にヒーロー認定試験会場に出向いたサイタマは、体力測定で次々と新記録を打ち立てるも筆記試験で壊滅的な成績を出し、結果はギリギリの合格。最低ランクであるC級ヒーローとして新たなスタートを切ることとなった。一方ジェノスは体力、筆記共に満点の合格。これまでの個人的な実績も考慮され、いきなりS級ヒーローに認定される。そしてこれを機に正式にサイタマに弟子入りしたジェノスは、サイタマに本気の手合わせを申し込むのだった…！

プロヒーローになって5日目。特にやることもなく自宅でゴロゴロしていたサイタマは、ジェノスから衝撃的な事実を知らされる。C級ヒーローには週に1度の活動報告ノルマがあり、それをこなせなければヒーローをクビになるというのだ。あわてて街へと繰り出し事件を探すサイタマだったが、そう都合よく怪人が出るわけもなく、刻一刻と期限が迫っていた。焦るサイタマの前に、彼をライバル視する音速のソニックが突然現れ、勝負を挑んでくる。事態をややこしく、そして悪化させるソニックに苛立つサイタマ。果たしてサイタマはヒーローの肩書を守ることができるのか！？

Z市に災害レベル竜の危機が迫っていた。宇宙から飛来した巨大な隕石が、Z市に向かって突如落下を始めたのだ。ヒーロー協会はS級ヒーロー達に対応を要請したものの、隕石が相手では為す術もなく事態は絶望的と思われた。招集を受けたジェノスもZ市のヒーロー協会支部に出向くが、職員は既に避難した後でビルはもぬけの殻。居合わせたS級ヒーローのシルバーファングから、このまま隕石が地上に激突すればZ市は壊滅すると聞かされるジェノス。恩師であるサイタマの住む街を守るため、ジェノスはたった一人、己の全てを賭して巨大隕石に立ち向かう事を決意するのだった。

J市の海辺に深海族と名乗る怪人の群れが上陸し、地上へと侵攻を始めた。A級ヒーローのスティンガーが激闘の末に彼らを殲滅するも、遅れて現れた深海王に一撃でやられてしまう。ニュースを見たサイタマとジェノスは急いでJ市に向かうが、深海王の居場所をなかなか特定できない上に、ひょんなことから二人ははぐれてしまう。そんな中、深海王の行く手を阻んだのは囚人服に身を包んだ謎の大男と、服役中のはずの音速のソニックだった。一方、C級ヒーローの無免ライダーも愛車のジャスティス号を駆り、必死に現場を目指していた。

深海王の襲撃を受け、恐怖のるつぼと化していた災害避難所に単身でジェノスが現れた。深海王と互角の戦いを繰り広げる彼の雄姿に避難所の人々は色めき立つが、ジェノスは子供を庇って深海王の吐き出した溶解液をモロに被り、形勢は一気に悪化してしまう。無情にもジェノスにトドメを刺そうとする深海王だったが、そこへもう一人のヒーローが現れる。だがそれは無免ライダーだった。C級ヒーローである無免ライダーと深海王とではあまりに実力差があり、人々は落胆する。しかしそれでも無免ライダーは果敢に深海王に立ち向かっていくのだった。

突如、S級ヒーロー達に非常召集がかかった。たまたまシルバーファングの道場を訪れていたサイタマとジェノスもシルバーファングに同行。A市にあるヒーロー協会本部へと足を運ぶと、会議室にはS級ヒーローの錚々たる面々が集結していた。そんな彼らの前でヒーロー協会の幹部が重い口を開く。100％的中するという予言者のシババワが、半年以内に「地球がヤバい」事態に陥るという予言を遺して亡くなったというのだ。会議室に緊張が漂う中、不意に本部ビルが轟音と共に揺れ、辺りは暗闇に包まれてしまう。やがて非常用電源に切り替わった会議室で彼らを待ち受けていたのは、今の一瞬でA市がほぼ壊滅したという事実であった。

A市上空に飛来した巨大宇宙船から地上に降り立ち、A級ヒーローのイアイアンを一蹴した戦闘員メルザルガルド。アトミック侍、金属バット、シルバーファング、ぷりぷりプリズナーらS級ヒーローが応戦するも、攻撃を受けるそばから肉体が再生するメルザルガルドには致命的なダメージを与えられず、戦いは難航する。一方、巨大宇宙船の内部に単独で進入したサイタマは、敵をなぎ倒し船内を破壊しながら中枢部を目指していた。サイタマの狼藉に業を煮やした敵幹部のゲリュガンシュプは、状況を打開するため再び地上への集中砲火を目論む。街を一瞬で破壊した悪夢のような惨劇が再びA市に牙を剥こうとしていた。

強大な超能力によって敵の砲撃を全て撥ね返した戦慄のタツマキ。激闘の末、強敵メルザルガルドの弱点を暴いたアトミック侍達。地上では事態が徐々に収束に向かい始める。そして全世界が固唾を飲んで宇宙船を見上げる中、その内部ではサイタマが暗黒盗賊団『ダークマター』の頭目ボロスと対峙していた。強さを持て余し、対等に戦える相手を求めてはるばる地球までやってきたというボロス。宿命ともいえるそんな敵を相手にサイタマは今度こそ本気を出すことができるのか？　人類の存亡をかけた壮絶な戦いの火ぶたが切られる。

ヒーロー協会に所属しヒーロー活動を開始したサイタマは、いつものようにジェノスを連れて買い物へ。そこで出会ったのは、ある組織から派遣されたという巨大ロボット機神G4と、それに対峙するキングだった。二人は戦いぶりを静観し、キングの実力を見極めようとする。同じ頃、ヒーロー協会は大予言者シババワが遺したメッセージを受け『地球がヤバい予言緊急対策チーム』を発足し、賞金首や荒くれ者からも戦力を集めようとするが…。

無数に集まった賞金首たちと、A級ヒーロー３人を全滅させ、ヒーロー協会へ宣戦布告をしてみせたガロウ。ヒーロー協会のシッチは、その凄まじい戦闘力に慄く。その頃、B級７位に昇格したサイタマを手下にしようと目論む地獄のフブキ（B級１位）は、誘いに興味を示さないサイタマに超能力で襲いかかる。ジェノスはしつこくサイタマを探す音速のソニックを「変質者」と即断。渾身のマシンガンブローとソニックの奥義が激突する。

ヒーロー狩りを続けるガロウは凶悪犯として指名手配される。かつてガロウを破門した「流水岩砕拳」の師匠でS級３位ヒーロー・シルバーファングは道場をたたみ、「旋風鉄斬拳」の達人で兄のボンブと共にガロウの捜索へ。一方のガロウはS級ヒーロー・タンクトップマスターと、その舎弟たちを相手にヒーロー狩りを始めていた。あまりの強さに戦慄するタンクトッパーたち。そこに現れたのはシルバーファングから破門された弟子チャランコだった。

ヒーロー協会重役のゼイミートがガロウに襲われた。警戒令が出される中、協会最高顧問のナリンキとその息子ワガンマの護衛を任されたS級ヒーロー・金属バットは、急襲してきたムカデ後輩とヒトトリグサを瞬殺。しかし、災害レベル竜に指定された凶悪怪人ムカデ長老が登場。さらにはガロウもその場に現れ戦況は急転する。そんな中、サイタマはチャランコが出場するはずだった武闘大会『スーパーファイト』に、カツラをかぶり変装して出場していた…。

災害レベル虎以上の凶暴な怪人たちが、各地で同時多発的に人々を襲い始めた。苦戦を強いられるヒーローたち。一方で徒党を組んだ怪人協会はヒーロー協会重役の誘拐を狙っていた。そして、金属バットとガロウとの熾烈なバトルを見ていた怪人フェニックス男はガロウを怪人協会へ誘う。同じ頃、サイタマが出場していたスーパーファイトが開幕。並み居る猛者たちの中に、過去４連覇を果たした優勝候補、冥躰拳の使い手スイリューの姿があった。

A級ヒーロー・イナズマックスがスイリューに一撃で敗れるという波乱で幕を開けたスーパーファイト。ジェノスは観客としてサイタマの試合を待っていたが、ヒーロー協会からの一報を受け、怪人たちが暴れる市内へと急行する。各地で起こる無数の怪人たちの猛攻にヒーローたちは防戦一方。その対応に追われ混乱する協会本部。そんな中、協会最高顧問ナリンキの息子ワガンマが怪人協会に誘拐されてしまう。

サイタマ、スイリューらベスト４が出揃ったスーパーファイトは大詰めを迎えていた。各地ではタツマキ、童帝、駆動騎士らS級ヒーローたちが事態の収束に乗り出し、怪人たちの勢力を押さえ込み始めていた。しかし、その戦況を怪人協会本部から見ていた幹部・ギョロギョロと、怪人王・オロチは、S級の戦いぶりを一笑に付すのだった。一方でアトミック侍は、ガロウ捜索の協力を仰ぐため、剣聖会屈指の大剣豪たちを集めていた。

スーパーファイト決勝戦はチャランコになりすましていたサイタマの反則負けという幕切れで、スイリューの優勝が決定する。そこへ現れたのは怪人化した初代スーパーファイト王者・ゴウケツ。ゴウケツの目的はスーパーファイトに参加している武術家たちを怪人協会に加入させることだった。次々と怪人化してしまう武術家たちに、スイリューはひとり立ち向かっていく。スーパーファイトの外ではヒーローたちの善戦むなしく各地は大きなダメージを受け、怪人協会の恐るべき謀略が明らかになる…。

怪人協会随一の強さを誇るゴウケツと怪人化したバクザンによって弄ばれるスイリュー。誰の助けも得られないことを悟り、絶望の底に叩きつけられた彼の前に現れたのは、サイタマだった。ほどなくして、ギョロギョロの計画の元、怪人協会の攻撃が収束していく。スーパーファイトで特に何も得られなかったサイタマ。強すぎるが故の悩みを打ち明けるサイタマに、キングはヒーローとしての高みを諭すのだった。

「怪人協会」からヒーローたちへの挑戦状とも取れる犯行声明が出された。人質となったワガンマ救出の猶予は3日。ヒーロー協会は怪人たちとの全面対決を前に準備に追われるが、メタルナイトは作戦協力の要請を拒否する。かたや、A級ヒーローのデスガトリングら8人の実力派たちは度重なる戦いで体力の残っていないガロウの追跡をしていた。連携の取れた連続攻撃に傷だらけとなったガロウはついに包囲されるのだが…。

8人のヒーローたちによってついに追い詰められたガロウ。しかし、一度の戦いで相手の戦闘スタイルを読み切る抜群のセンスをもつガロウは反撃を開始。徐々に形勢を逆転し、ヒーロー8人を全滅させる。そこへ駆けつけたのは、新パーツを換装しパワーアップしたジェノスだった。満身創痍のガロウは容赦のないジェノスの猛攻撃を受ける…が、その時、無数の怪人協会の刺客が突如として現れ、ガロウを奪取するべくジェノスに襲いかかる！

ガロウを追っていたシルバーファングとボンブがジェノスに合流。ボンブは無数の怪人たちを旋風鉄斬拳で倒していく。既に息も絶え絶えのガロウは、かつての師匠・シルバーファングの鬼気迫る流水岩砕拳に手も足も出ない。強烈な連続攻撃を受け、意識を朦朧とさせるガロウ！　そこに急襲を仕掛けたのは災害レベル竜の大怪蟲・ムカデ長老だった。さらにキング、サイタマも参戦！　壮絶バトルはあまりに意外なクライマックスを迎える！