1999年10月3日、K-1 GRAND PRIX '99 開幕戦に出場し、GP1回戦でマイク・ベルナルドからハイキックでいきなりダウンを奪うと、一気にラッシュを叩き込んで2つ目のダウンを奪って1RKO勝ちし、K-1四天王の1人を倒したことで一躍脚光を浴びるようになる。

1999年6月12月5日のK-1 GRAND PRIX '99 決勝戦では、GP準々決勝で武蔵に2RKO勝ち、GP準決勝でサム・グレコに2RKO勝ちして決勝まで駒を進めたが、武蔵戦で痛めた脇腹を、続くグレコ戦でも痛めて肋骨を骨折してしまったこともあり、GP決勝ではアーネスト・ホーストにその部分を攻められボディ打ちで3RKO負けを喫し、グランプリ準優勝に終わった。

その後リングネームをミルコ・クロコップに変更。かつてのやや細身で迫力を欠く体格はビルドアップされ、更にポーカーフェイスの精悍な顔つきも相まって「ターミネーター」のニックネームが定着。この頃から人気と実力を兼ね備えた、次世代を担う選手として注目されるようになった。

2000年3月19日、K-1 BURNING 2000で天田ヒロミと対戦。元暴走族と現役警察官の対決だったため、天田は暴走族を、ミルコは警官隊を引き連れて入場するというパフォーマンスを披露。試合は4RでミルコがKO勝ちを収めた。

2000年6月3日、アンディ・フグの母国スイスでの引退試合の相手を務める。お互い決定打に欠けたが、手数で勝ったフグに判定負けとなった。少年の頃からフグに憧れていたというミルコは、母国引退となるフグを笑顔で讃えた。

2000年10月9日、K-1 WORLD GP 2000 in FUKUOKAのGP予選トーナメントでは、GP予選1回戦でグラウベ・フェイトーザに判定勝ち、GP予選準決勝で天田ヒロミに判定勝ちを収めた。GP予選決勝の相手はマイク・ベルナルドであったが、この予選トーナメントのファイナリスト2人が12月の決勝大会へと出場できるため、すでに出場権を手に入れていたミルコは、準決勝で怪我をしたこともあり決勝では無理をせず1R終了後に自らタオル投入によるTKO負けを選択し、ベルナルドにリベンジを許した。
K-1 GP 2000

2000年12月、K-1 WORLD GP 2000 決勝戦では準々決勝でアーネスト・ホースト相手に延長まで持ち込むものの、延長に入ると試合をリードされ0-3で判定負けに終わった。

2001年3月17日、K-1 GLADIATORS 2001のピーター・アーツ戦では、序盤にハイキックとパンチのラッシュでめ込むも、後半は膝蹴りを受けスタミナ切れを起こし失速。最後はクリンチ合戦となった末、ミルコが辛くも競り勝ち2-0で判定勝利を収めた。

2001年6月16日、K-1 WORLD GP in MELBOURNEではGP予選トーナメント1回戦でマイケル・マクドナルドと対戦。相手を格下と見て、試合中に腕を回すなどの挑発行為や余裕な態度をとったが、クリンチをして密着した状態でマクドナルドが放ったパンチを顎に受けてグラついてしまいそのままラッシュを受けて1RKO負けし、まさかの初戦敗退となった。
K-1・総合格闘技両立時代
総合格闘技初挑戦での番狂わせ

2001年8月19日、K-1 ANDY MEMORIAL 2001にて、K-1と猪木軍との対抗戦に出場することとなり、3分5Rの総合格闘技ルールで猪木軍のエース藤田和之と対戦する。試合は下馬評を覆して、藤田のタックルに膝蹴りを合わせ大流血に追い込み、ドクターストップによるTKO勝ちを収めた。後にミルコがこの勝利が大きな転機となったとコメントしているように、この総合格闘技ルールでの番狂わせの勝利が、後の総合格闘技への転向、そしてPRIDE出場に繋がることになった。

2001年10月8日、K-1 WORLD GP 2001 in FUKUOKAの敗者復活トーナメントに出場予定だったが、9月11日のアメリカ同時多発テロ事件発生の影響で、当時警察官だったミルコは国内待機となり、GP出場は断念した。
PRIDE初出場

2001年11月3日、PRIDE.17でPRIDE初出場を果たした。藤田戦と同じルールでの高田延彦との対戦は、高田が試合序盤でミルコにローキックをカットされ右足踵骨を骨折したためリングに腰を降ろしてグラウンドに誘う作戦に出たが、ミルコはこれを拒否し続け、猪木アリ状態のまま試合は終了しドローとなった。ミルコは試合後、激怒し「気分が悪い。高田はチキンだ。」「藤田は本物のファイター。高田は偽者のファイター。」と罵倒したが、後に高田が足を骨折していたことを知ると謝罪に近い言葉を述べ、互いのわだかまりはなくなっている。

2001年12月31日、INOKI BOM-BA-YE 2001にてプロレスラーの永田裕志と総合格闘技ルールで対戦し、試合開始から21秒後には左ハイキック一撃で永田をリングに沈め、藤田、高田、永田の3人のプロレスラーを倒したことでプロレスハンターと呼ばれるようになった。
ハント戦

2002年3月3日、K-1 WORLD GP 2002 in NAGOYAで、前年GP王者マーク・ハントと対戦。試合序盤はハントを翻弄し、3Rに左ハイキックでダウンを奪う。後半はハントのプレッシャーや打撃により逆襲を受ける展開となってしまうが、その反撃をかわし切り判定で勝利した。試合後には笑顔一つも見せずにハントの祝福にも首を振っていたが、この勝利を以って改めて「K-1王者になりたい」と語り、一方で総合格闘技への本格的な挑戦も語った。
ヴァンダレイ第1戦

2002年4月28日、PRIDE.20では総合格闘技4戦目でPRIDEミドル級王者ヴァンダレイ・シウバと対戦。ルールは3分5R判定なし、グラウンドでの膠着はスタンドからのリスタートという、総合格闘技経験の浅い当時のミルコに配慮した特別ルールとなった。また両者の体重差に配慮して98kg契約だったが、計量時はミルコよりもシウバの方が体重を上回っていた。この試合は「K-1vsPRIDE 頂上決戦」と評された。ミルコの左ミドルキックがシウバの脇腹を抉り、紫色に腫れ上がらせた一方、シウバもミルコから数度のテイクダウンを奪い、スタンドでも手数で上回っていた。試合は規定により時間切れドローに終わった。

再びK-1に戻り、2002年4月7月14日のK-1 WORLD GP 2002 in FUKUOKAでは、後のGP王者レミー・ボンヤスキーにパンチの連打で2RTKO勝ちし、GP本戦の切符を手に入れた。
桜庭戦

2002年8月28日、「Dynamite!」で桜庭和志と対戦。ルールはミルコにとっては初めての5分3R制のPRIDE特別ルールとなった。なお、体重は20kg近くミルコが重かった。2Rに桜庭にテイクダウンを奪われたものの、脱出の際の顔面への蹴り上げで桜庭の右目が腫れ上がり、眼窩底骨折の疑いでドクターストップがかかりTKO勝利となった。その後椎間板ヘルニアを理由にK-1 WORLD GP 2002を欠場、長期休暇を取ったこの間に長年交際してきた女性と結婚している。

2002年12月31日、INOKI BOM-BA-YE 2002にて藤田和之と総合格闘技ルールで再戦し、危なげない試合運びで判定勝ちを収め返り討ちにした。
サップ戦

2003年3月30日、K-1 WORLD GP 2003 in SAITAMAで当時人気絶頂にあったボブ・サップと対戦。体格差に押されるシーンが多かったがフットワークでいなし、左ミドルからのワンツーでKO勝利を挙げた。勝利直後、普段はKO勝利してもクールなミルコにしては珍しくコーナーポストに駆け上がり、雄たけびを上げた。風邪を引いて高熱でコンディションが悪く、母国クロアチアでは衛星生中継されている重圧から開放されてうれしかったと後に語っている。なお、クロアチアでのこの試合の視聴率は約50%であった。試合後、サップは右眼窩内側壁骨折および右眼窩壁骨折と診断された[5][6]。この試合を境にミルコはK-1、キックボクシングからしばらく離れる。
PRIDE

2003年6月8日、PRIDE.26からPRIDEシリーズに本格参戦。当時のPRIDEヘビー級3強の1人と言われたヒース・ヒーリングと通常PRIDEルール(1R10分、2・3R各5分)で対戦、強烈な左ミドルキックからのパウンドでTKO勝利。試合後、ミルコはPRIDEヘビー級王者エメリヤーエンコ・ヒョードルへの挑戦を宣言した。なおこの試合は母国クロアチアでも当日ディレイ放送され70%超の視聴率を叩き出した。

2003年8月10日、PRIDE GRANDPRIX 2003 開幕戦でイゴール・ボブチャンチンに強烈な左ハイキックで1R1分29秒KO勝利。ヒョードルの保持するヘビー級王座への挑戦を決定的なものとした。10月5日には「PRIDE武士道」に出場。自らこの試合をタイトルマッチのためのクールダウンと称し、ドス・カラスJrに左ハイキックで1R46秒でKO勝利。
ノゲイラ戦

2003年11月9日、PRIDE GRANDPRIX 2003 決勝戦ではPRIDEヘビー級暫定王座決定戦としてアントニオ・ホドリゴ・ノゲイラとの対戦を迎えた。本来ならこの大会でPRIDEヘビー級王者エメリヤーエンコ・ヒョードルに挑戦するはずだったものの、ヒョードルの怪我によりノゲイラとの暫定王座決定戦となった。1Rはミルコが打撃で圧倒し、終了間際に左ハイキックを放ち、完全な形ではないがヒットさせてノゲイラからダウンを奪った。2R開始直後、初めてテイクダウンを奪われるとパウンドを浴びて、グラウンドの展開から脱出しようとした際にノゲイラに腕ひしぎ十字固めを極められてしまいタップアウト負け。これにより総合格闘技での無敗記録がストップした。試合後のセレモニーで、暫定王者のベルトを与えられるノゲイラの姿を見つめながら、ミルコはリングの片隅で涙を浮かべていた。

2003年12月31日のINOKI BOM-BA-YE 2003に出場し高山善廣と対戦予定だったが、直前になって出場をキャンセルした。

2004年2月1日、PRIDE.27でロン・ウォーターマンと対戦。序盤からいきなりテイクダウンを奪われるも、スタンドに復帰後すぐさま左ハイキックでダウンを奪い、サッカーボールキックを浴びせてKO勝利。2週間後、2月15日のPRIDE 武士道 -其の弐-では山本宜久にTKO勝利する。
PRIDE GP 2004

2004年4月25日、PRIDE GRANDPRIX 2004 開幕戦のPRIDEヘビー級GP1回戦でケビン・ランデルマンと対戦。満を持して臨んだトーナメントで、ミルコを優勝候補に挙げる声も多かったが、1R1分57秒、左フックからのパウンドでまさかの失神KO負けを喫した。

2004年8月15日、PRIDE GRANDPRIX 2004 決勝戦ではPRIDEヘビー級王者ヒョードルの弟のエメリヤーエンコ・アレキサンダーと対戦、20キロ以上の体重差を問題にせず左ハイキックでKO勝利。観衆はミルコの鮮烈な復活劇を歓喜で迎えた。この勝利により、ミルコはPRIDEトップ戦線への返り咲きを果たした。

2004年10月31日、PRIDE.28でパンクラス無差別級王者、元UFC世界ヘビー級王者のジョシュ・バーネットと対戦。