サトシのダクマが連撃の型のウーラオスに進化した後も彼らはヨロイ島で修業を続けていた。その間にサトシのココガラがアオガラスに進化し、ハルカがダイマックスバンドをミツバから受け取った。
マオ「大分パワーアップしてきたね。」
サトシ「ああ、みんな絶好調だ！」
そんな時ハルカがサトシに話しかける。
ハルカ「ねえサトシ、ちょっといいカモ？」
サトシ「どうしたハルカ？」
ハルカ「これ覚えてる？」
ハルカは自分の左腕に虹色の宝石が埋め込まれたバングルを見せる。
サトシ「それは前に俺がハルカに誕生日プレゼントであげたアクセサリーと一緒に渡したメガバングル。」
ハルカ「うん。サトシのリザードンやゲンガーってメガシンカやキョダイマックスできるでしょ？」
サトシ「ああ。」
ハルカ「私のフシギバナとカメックスもキョダイマックスできるようになったからバシャーモだけしゃなくて・・・。」
サトシ「フシギバナやカメックスもメガシンカさせたいってことか。」
ハルカ「うん。」
リーリエ「確かにサトシは状況に応じてバトルしてますね。」
ヒカリ「私も一応ミミロップナイトを持ってるわ。」
シンジ「俺もボスゴドラナイトを戦力として入れている。」
マサル「でもメガストーンをゲットするとなると簡単なことじゃないよね？」
マリィ「うん、闇雲に探しても見つからないけん。」
サトシ「それじゃあさ！」
全員「？」
サトシ「メガ島に行ってみないか?」
ノゾミ「メガ島？」
シンジ「確かカロス地方に新しくできた島だな。」
セレナ「私も聞いたことがある。突然現れた島でメガストーンが大量に発見されてるんだって。」
アルセウス「そのためメガシンカが可能な野生ポケモン達が集まっていると聞く。」
ケルディオ『サトシのルカリオのルカリオナイトもコンコンブルがその島で見つけたんだっけ？』
サトシ「ああ。そこに行けばフシギバナとカメックスのメガストーンが見つかると思ってな。」
アルセウス「そういうことか。」
ハルカ「私行く！メガ島に！」
サトシ「よし、じゃあ明日行こうぜ！」
ハルカ「うん！サトシ、ありがとー！」
ガバッ！！ムニュ！！
サトシ「うおっ！？///また大胆な///」
ハルカ「えへへ///」
ハルカがサトシに抱きつき、その際ハルカの『御立派』なものがサトシの胸板に押し当てられて形を変えている。それを見たセレナ達は面白くなさそうにジト目で睨んでいた。ノゾミとスイレンに関してはハルカのスタイルを羨ましそうに見ていた。
こうしてサトシ達はハルカのためにカロス地方に向かうことになった。但し、シンジ、ノゾミ、スイレン、カキ、マーマネは残ることになった。
次の日、サトシ達はカロス地方のメガ島に向かうことになった。今回サトシの連れて行くポケモンは以前シャラジムを訪れたことのあるルカリオ、メガストーンを持っていないミュウツーとタブンネ、ラティアス。そして旅のお供としてまだ他の地方に行ったことのないウーラオスとカモネギ、アオガラスも連れて行くこととなった。因みにアオガラスは最近流行りのポケモンボックスに入っている。ピカチュウは残ったメンバーのまとめ役としてヨロイ島に残ってもらうことになった。同行するメンバーはセレナ達とケルディオとなり、ピカチュウはアルセウスと一緒に残ったメンバーのまとめ役としてヨロイ島に残ってもらうこととなった。
サトシ「ピカチュウ、アルセウス、皆を頼む。」
ピカチュウ『任せて！』
アルセウス「お前達が戻ってくるまでサトシのポケモン達は私達が鍛えておこう。」
セレナ「久しぶりだなカロス地方。」
ヒカリ「そっか、セレナにとっては里帰りなんだね。」
ラングレー「アタシも時間があったら氷かフェアリーのポケモンゲットしよ。」
マオ「なんだか楽しみ！」
リーリエ「そうですね！」
ハルカ「ちょっと！今回の目的は私のメガストーン探しなんだからね！」
ケルディオ『分かってる。』
サトシ「それじゃカロス地方目指して・・・。」
サトシ・セレナ・ハルカ・ヒカリ・ラングレー・マオ・リーリエ・ケルディオ「「「「「「「『レッツゴー！！！！！』」」」」」」」
こうしてサトシ達はフシギバナとカメックスのメガストーンを探すためにヨロイ島からガラルの空港に赴き、カロス地方に向かうのだった。目的地はシャラシティ近海の島《メガ島》である。
カロス地方・シャラシティ
ガラル地方を出発して数日が経ち、サトシ達はカロス地方の空港に到着した後バスに乗ってシャラシティへとやって来た。因みにケルディオはミュウツーがサイコパワーで浮遊させてサトシ達の後を追いかけた。
コルニ「サトシ～！セレナ～！」
サトシ・セレナ「「コルニ！」」
シャラジムに着くとジムの前にシャラジムのジムリーダー・コルニとパートナーのルカリオ、コルニの祖父であるメガシンカ親父ことコンコンブルの姿があった。
コンコンブル「久しぶりじゃなサトシ君。」
サトシ「はい。すみません、突然訪問するって連絡して。」
コンコンブル「いいんじゃよ、いつでも歓迎じゃ。」
コルニ「元気そうだねセレナ。」
セレナ「うん。」
コルニ「それで貴女が今回メガ島に用があるっていう・・・。」
ハルカ「初めまして、サトシの彼女の1人のハルカ。よろしく。」
ヒカリ「私ヒカリ。」
ラングレー「ラングレーよ。」
マオ「アタシはマオ。」
リーリエ「リーリエです。」
サトシ「皆俺の彼女なんだ。」
コルニ「そうなんだ。・・・あれ、ピカチュウは？」
サトシ「アルセウスと一緒にヨロイ島に残ってもらったよ。」
コンコンブル「確かにあそこは修行には持って来いの場所じゃな。さあ、船の準備はできておる。すぐに出発するぞ。」
コンコンブルが用意した船に乗り込みメガ島へと出発した。
コンコンブル「サトシ君、PWCSの調子はどうだ？」
サトシ「はい、今はスーパークラスであと少しでハイパークラスに昇格できます！」
コンコンブル「そうか。」
コルニ「私達も負けてられないね！」
ルカリオ（コルニ）「ヴォル！」
セレナ「そういえばコルニも参加してるんだったね。」
コルニ「ええ！」
ラングレー「ライバル多いわねサトシ。」
ハルカ「今までの旅でいっぱいできたからね。」
ヒカリ「うんうん。」
リーリエ「お兄様もその1人ですしね。」
マオ「そうだね。」
コンコンブル「さあ、もうすぐ着くぞ。」
そうこうしているうちにメガ島に到着した。
コンコンブル「気を付けるのじゃぞ。」
サトシ「はい。」
ヒカリ「行ってきまーす。」
ハルカ「ハルカ探検隊、出動！」
サトシ「お、久しぶりに聞いたなそれ。」
コルニ「何それ？;」
サトシ「ハルカが昔よくやってたやつ。」
ラングレー「早く行きましょ。」
マオ「でもどうやって探す？」
リーリエ「そうですね。」
サトシ「それなら大丈夫。」
セレナ「え？」
サトシ「ハルカ、フシギバナとカメックスを出すんだ。」
ハルカ「え？分かった。」
疑問に思いながらもハルカはサトシの言う通りフシギバナとカメックスをボールから出した。
ポーン！
フシギバナ「バナ！」
カメックス「カメス！」
サトシ「次にメガバングルを着けてフシギバナ達と手を合わせるんだ。」
ハルカ「うん。フシギバナ、カメックス。」
フシギバナ「バナ。」
カメックス「カメ。」
ハルカはメガバングルを装着しフシギバナやカメックスと手を合わせた。
サトシ「そしてフシギバナ達が心を研ぎ澄まして島全体を感じ取れば場所を絞り出せる筈だ。」
マオ「フシギバナ達が探すってこと？」
サトシ「前にコルニが言ってたんだ。ポケモンとメガストーンは惹かれ合うって。もしかしたらフシギバナ達の思いがメガストーンに届けば、メガストーンもそれに反応するかなって思って。」
リーリエ「成程。」
コンコンブル「コルニよ、これはサトシ君の方が一枚上手のようだな。」
コルニ「ぶう〜///」
サトシ「ハルカ。」
ハルカ「うん。フシギバナ、カメックス、やってみて。」
フシギバナ「バナ。」コクリッ
カメックス「カメス。」コクリッ
フシギバナ達はサトシの言われた通りに心を落ち着かせて感覚を研ぎ澄ます。・・・すると。
ドン！ドン！
フシギバナ「バナ！」
カメックス「カメス！」
ハルカ「あ！」
サトシ「感じたみたいだな。」
フシギバナ達は何かを感じ取り、感じ取った方向を向いた。
コルニ「見つけたの！？」
ハルカ「まだ正確な位置は分からないけど、大体絞れたみたいかも！」
サトシ「じゃあ後はフシギバナとカメックスの感じたままその気配を辿って行けばいいな。」
ハルカ「フシギバナ、カメックス、お願い。」
フシギバナ「バナ。」コクリッ
カメックス「カメス。」コクリッ
フシギバナ達が己の感じ取ったままの道を進みサトシ達はその後に続く。だがこの時、待機していたコンコンブルが不敵な笑みを浮かべていたことには誰も気がつかなかった。
フシギバナとカメックスが導くままにサトシ達は途中でバトルをしているポケモン達とも遭遇しながらメガ島の険しい道のりを進みメガストーンを探し続けた。
サトシ「大分進んで来たな。」
リーリエ「中々見つかりませんね。」
マオ「うん。」
ラングレー「まあ、簡単に見つかったら苦労しないわよね。」
ヒカリ「でも冒険って感じがしてきた！」
ハルカ「ワクワクだ！」
コルニ「もうハルカとヒカリったら;」
サトシ「ハハハ！」
その様子をミュウツーとケルディオが上空で見ていた。
ミュウツー『相変わらず吞気だな。』
ケルディオ『まあいいじゃん、楽しそうだし。』
ミュウツー達が見ているのも知らないサトシ達は更に先を進んでいた。だが、
ズル！
サトシ「うわぁ！？」
セレナ「サトシ！ってキャ！？」
サトシは油断して氷の地面に足を滑らせて下に滑り落ちてしまい、セレナも一緒に落ちてしまう。だが上空で待機していたミュウツーにサイコパワーで救出された。
サトシ「助かったぜミュウツー。」
セレナ「ありがとう。」
ミュウツー『礼を言われる程ではない。』
ハルカ「2人共大丈夫！？」
サトシ「ああ。」
セレナ「なんとか。」
ケルディオ『でも何でここ凍ってたんだろう？』
ミュウツー『答えはあれだ。』
ミュウツーが差した方向に白い1体のポケモンがいた。
ユキノオー「ユーノ！」
サトシ「ユキノオーだ！」
ラングレー「ラッキー！ゲットしておかないと！行け、キリキザン！」
ポーン！
キリキザン「キザ！」
ラングレー「金属音！」
キリキザン「キザー！」
ユキノオー「ユノー！？」
ラングレー「シザークロス！」
キリキザン「キーザ！」
ユキノオー「ノー！？」
ラングレー「今よ！行きなさい、モンスターボール！」
ユキノオーが弱ったところでラングレーがモンスターボールを投げる。ユキノオーがボールに入るとしばらく揺れて、ポンッという音が鳴った。
ラングレー「ユキノオー、ゲット！」
サトシ「やったなラングレー！」
ラングレー「ええ、この島に来てよかったわ！」
サトシ「ドラゴンバスターにまた一歩だな！」ニコ
ラングレー「あ、ありがとう///」
ラングレーはサトシに褒められて顔を赤くして照れる。少々トラブルがあったがそこからは順調にメガストーンがある場所に進んでいった。
フシギバナ「バナ！」
カメックス「カメス！」
暫く進むと複数の鋼の石がそびえ立つ場所にたどり着いた。
サトシ「何だここ？」
リーリエ「石がいっぱいです。」
マオ「うん、すごい数。」
コルニ「鋼の森だよ。」
ヒカリ「鋼の森？」
ミュウツー『所々微弱だがそれぞれの石から強い気配を感じる。』
ケルディオ『それじゃあこの中にメガストーンが？』
ミュウツー『可能性はある。』
フシギバナとカメックスはそれぞれ石に近づいた。
ハルカ「もしかしてそこに・・・。」
ラングレー「メガストーンがあるのね！？」
サトシ「ハルカ、早速！」
ハルカ「うん！フシギバナ、ソーラービーム！カメックス、ハイドロポンプ！」
フシギバナ「バーナ！」
カメックス「カーメ！」
ドゴーン！
フシギバナとカメックスは自身の大技で石を砕いた。すると光り輝く2つのメガストーンが現れた。
サトシ「もしかしてあれが！？」
ミュウツー『フシギバナイトとカメックスナイトで間違いないだろう。』
ヒカリ「でも何で落ちてこないの！？」
マオ「しかも浮いてる！？」
そう、2つのメガストーンは落ちてこずにそのまま宙に浮いていた。
ラングレー「これって、サイコパワー！？」
ミュウツー『間違いないな。』
ケルディオ『でも一体誰が？』
フーディン「フーディン！」
サトシ「フーディン！？」
リーリエ「フーディンのサイコキネシスで浮いていたのですね！」
???「およよおよよ！！」
サトシ「誰だ！？」
突然サトシ達の前にキーストーンが埋め込まれた杖を持った謎の老人が現れた。
メガシンカ仙人「掴みはばっちり！！メガシンカ仙人とは儂のことだー！！」
ハルカ「メガシンカ仙人！？」
ヒカリ「酷いネーミング;」
サトシ「なあコルニ、あの人もしかして・・・。;」
コルニ「うん、間違いないよ;」
ミュウツー『何をやっているのだ一体？』
ケルディオ『あはは(￣▽￣;)』
サトシとコルニ、ミュウツー、ケルディオは目の前の人物の正体に気づいていた。
メガシンカ仙人「メガストーンを手に入れたければ、このに勝ってみせよ！」
ラングレー「実力で手に入れろってことね。」
ヒカリ「ハルカが見つけたものなのに！」
ハルカ「大丈夫よ皆。」
マオ「でも。」
ハルカ「サトシならこれも試練だと思って挑むわ。だったら私も乗り越えてみせる！」
リーリエ「・・・分かりました！」
サトシ「頑張れよ！」
ハルカ「フシギバナ、カメックス！ステージ・オン！」
フシギバナ「バナ！」
カメックス「カメッス！」
2つのメガストーンを賭けたバトルが始まった。
メガシンカ仙人「およよ！フシギバナイトとカメックスナイト争奪バトル始まりじゃ！！」
ラングレー「調子狂うわね;」
ヒカリ「変な人;」
メガシンカ仙人「みんなのヒーロー、メガシンカ仙人の本領発揮！いざ、メガシンカ！！」
メガシンカ仙人は杖のキーストーンに触れると、キーストーンから光が放たれると同時に掲げる。それに反応するようにフーディンが持っていたフーディナイトもひかり出し2つの石から光の糸が出現し、空中で結びつく。するとフーディンは光に身を包み込まれ姿を変える。
メガフーディン「フー、ディン！」
セレナ「メガフーディン！」
リーリエ「あれが！」
マオ「スプーンがいっぱい。」
ハルカ「行くわよ！フシギバナ、蔓の鞭！カメックス、高速スピン！」
フシギバナ「バーナ！」
カメックス「カメー！」
メガシンカ仙人「およよスプーンを打て！！」
メガフーディン「フーディ！」
最初に動いたのはフシギバナとカメックスだが、メガフーディンは焦らずにスプーンを飛ばして技を相殺させる。
メガシンカ仙人「サイケ光線！」
メガフーディン「フディ！」
ハルカ「躱して！」
フシギバナ「バナ」
カメックス「カメッス！」
ハルカ「フシギバナ、すてみタックル！カメックス、アクアテール！」
フシギバナ「バーナ！」
カメックス「カメース！」
メガシンカ仙人「トライアターック！」
メガフーディン「フディ！」
バシュン！バシュン！バシュン！
フシギバナ「バナ！？」
カメックス「カメ！？」
ハルカ「フシギバナ！？カメックス！？」
ラングレー「強いわね、あのメガフーディン。」
リーリエ「はい。」
マオ「完全に相手のペースだよ。」
フシギバナ「バナ！？」ビリビリ！
カメックス「カメス！？」ボー！
ケルディオ『マズイ！トライアタックは麻痺、火傷、氷のいずれかの状態にする技、さっき技を受けたことでフシギバナとカメックスが麻痺と火傷になったんだ！』
ミュウツー『このピンチをどう切り抜けるかだな。』
サトシ「ハルカを信じるしかないな。」
ヒカリ「ハルカ頑張って！」
ハルカ「私は負けない！サトシやポケモン達、皆と一緒に夢を掴む！」
BGM：私、負けない!～ハルカのテーマ～
メガシンカ仙人「トライアターック！」
メガフーディン「フーディ！」
ハルカ「カメックス、ハイドロポンプ！そしてそのまま高速スピン！」
カメックス「カーメスーー！」
メガフーディン「フディ！？」
メガシンカ仙人「およよ！？」
カメックスはその場でハイドロポンプを使い、高速スピンで回転すると渦を描くように動きトライアタックを封じてメガフーディンにダメージを与える。
ミュウツー『これは！？』
ケルディオ『カウンターシールド！？』
サトシ「いいぞハルカ！」
ヒカリ「いけいけ！」
ハルカ「フシギバナ、花びらの舞！」
フシギバナ「バーナフー！」
メガフーディン「フディー！？」
フシギバナが花びらの舞を使うと、メガフーディンにダメージを与えると同時にフシギバナイトとカメックスナイトが吹き飛ぶ。
ハルカ「今よ！」
フシギバナ「バナ！」
カメックス「カメ！」
その隙に2体が自身のメガストーンを掴み取る。
フシギバナ「バナー！」
カメックス「カメース！」
ハルカ「フシギバナイトとカメックスナイト、ゲットかも！」
セレナ・ヒカリ・ラングレー・マオ・リーリエ「「「「「やったー！！」」」」」
サトシ「やったなハルカ！」
コルニ「おめでとう！」
メガシンカ仙人｢にひ！！ははははー！！｣
一同「ん？」
メガシンカ仙人｢皆のヒーロー、メガシンカ仙人の正体は！！｣バッ！
ハルカ・ヒカリ・ラングレー・マオ・リーリエ「「「「「ああー！？」」」」」
セレナ「コンコンブルさん！？」
サトシ・コルニ・ケルディオ「「『やっぱり。』」」
ミュウツー『全く。』
コンコンブル「ははは！ちょっとしたサプライズじゃ！見事だったぞハルカくん。」
何とメガシンカ仙人の正体は待機していた筈のコンコンブルだった。
セレナ「どうしてこんなことを？」
コンコンブル「ハルカくん達の絆を確かめるためじゃ。聞いた話だとハルカくんはバシャーモでメガシンカできるらしいが、フシギバナとカメックスにもそれ程の絆があるか気になってな。」
ラングレー「そうだったんだ。」
マオ「あれ？でもサトシ達はメガシンカ仙人がコンコンブルさんって気づいてたの？」
サトシ「ああ。」
ケルディオ『言うタイミングがなくて言いそびれちゃった。』
ミュウツー『すまんな。』
リーリエ「まあ、結果オーライということで;」
ハルカ「これからも頑張ろうね、フシギバナ！カメックス！」
フシギバナ「バナ！」
カメックス「カメッス！」
こうしてハルカはフシギバナとカメックスの新たな切り札を手に入れ戦力の幅が広がった。その後サトシはルカリオと協力してタブンネナイトとラティアスナイト、ミュウツナイトXを手に入れてメガ島を後にするのだった。