99年、ヴォーカリスト脱退。後任に世界最高峰メタル･ヴォーカリストの1人、Andy B. Franckを迎え入れる。Franck加入から2ヶ月後にMETAL BLADE RECORDSと契約し、待望の3rdアルバム｢Ambiguity｣がHOUSE OF MUSIC STUDIOにてDirk SchlachterとSascha Paeth(RHAPSODY)らのプロデュースのもと制作された。ARMORED SAINT、KING DIAMOND等とフェスティバル出演が続き、バンドの人気を不動のものとした。
2001年10月、4thアルバム「Metus Mortis」をリリースし、各メタル誌で"Album of the Month"と称された。GRAVE DIGGERとTIERRA SANTAとのツアー、更にヨーロッパ中のフェスへの出演やSAXONとのライヴもあり、BRAINSTORMは更なる地位を獲得。
2003年3月、再びHOUSE OF MUSIC STUDIOへと戻り、5thアルバム｢Soul Temtation｣を制作。EDGUYとの大規模なツアーや世界中のフェスティバルへの出演が続き、メタル･アクトのトップ集団に君臨する事となった。
そして6作目となる「Liquid Monster」は、ヨーロッパの超常現象とまで言われる力作だ。EDGUY、MORGANA LEFAY、SOLITUDE AETERNUS、SKYCLAD、NOCTURNAL RITES等と大規模なヨーロッパ・ツアーを重ね、ヨーロッパ中でフォロワー層を築いた。BRAINSTORMは2003年と2004年にはSWEDEN ROCK、アメリカのPROGPOWER、ドイツのWACKEN OPEN AIR等、ヨーロッパとアメリカが誇る有数のメタル･フェスティバルへ多数出演。そして彼らは2004年11月、あの有名なHOUSE OF MUSIC STUDIOにて、Achim Kohlerプロデュースのもと「Liquid Monster」をレコーディング。リリース間もなく、BRAINSTORMは2005/2006 ｢INSIDE THE MONSTER｣ヘッドライニング･ワールド･ツアーを敢行する。
