1454年、セルビア公ジュラジ・ブランコヴィチに割譲した領土の返還を求めるが、ジュラジは返還を拒否する。メフメトはセルビアに遠征してジュラジに改めて臣従を誓わせ、1455年の冬からベオグラード遠征の準備を始める[56]。
1456年7月にメフメトが率いるオスマン軍はベオグラードの包囲を開始、メフメトとオスマン軍の指揮官の多くは容易にベオグラードを攻略できると楽観視していた[57]。しかし、ドナウ川に浮かぶオスマン軍の艦船はドミニコ会修道士カピストラヌスが率いる民衆の攻撃を受けて壊滅し、ベオグラード市内に突入したオスマン軍はフニャディ・ヤーノシュの反撃を受けて惨敗した[58]。従軍していたイェニチェリの多くが戦死し、メフメト自身も額に傷を負った[59]。
帰国後すぐ、メフメトはベオグラードでの敗戦を忘れるかのように、息子バヤズィトとムスタファの割礼の式日にエディルネで大々的に宴会を開いた[60]。宴会では学者たちのディベート、スポーツの競技会が開かれ、町の住民に金銭を与えた[60]。
オスマン軍が撤退した翌日にフニャディは没するが、この敗戦によってオスマン帝国はハンガリーへの進出を一時中断しなければならなかった[55]。ベオグラードでの攻防はキリスト教国にオスマンに対する勝利を確信させ[61]、敗れたメフメトは征服の目標をバルカン半島の内部に変えた[62]。また、教皇カリストゥス3世はヨーロッパの王侯に反オスマン連合の結成を呼び掛けたが、結成に積極的な返事は得られなかった[63]。 ベオグラードの敗北と同じ時期[64]、ルーマニアのモルダヴィアを臣従させ、モルダヴィアに和平と引き換えの貢納金を課した。また、ワラキアではヴラド・ツェペシュが公に即位する。メフメトはワラキアとモルダヴィアを臣従国としながらも、一定の自治を認めていた[65]。
ペロポネソス半島、セルビアの征服
1458年春にメフメトはペロポネソス半島に進軍し、ソマスとディミトリオスは宮廷から逃走する。ペロポネソス半島の3分の1がオスマン帝国の支配下に入り、ソマスとディミトリオスには領土の保持と引き換えに貢納金を課した[67]。また、メフメトは遠征で獲得したパトラの立地と整備された海港に着目し、町を発展させるために住民を保護し、特権を付与した[68]。同年、オスマンの将軍エメルの策略により、アテネ公国がオスマン帝国に併合される[69]。
1458年初頭よりセルビアは後継者問題で反オスマン派と親オスマン派に分かれており、親オスマン派はメフメトにセルビアへの派兵を要請した[70]。初めにセルビアには宰相マフムト・パシャを司令官とする軍隊が派遣され、メフメトはモレアス遠征の帰路にマフムト・パシャの軍に合流する。1459年春にオスマン軍はボスニア王ステファン・トマシェヴィッチよりスメデレヴォを譲渡され[71]、ベオグラードを除くセルビアの征服を完了した[72]。
さらにセルビアの征服はボスニアへの進出の足掛かりとなり、1460年にボスニアへの攻撃を開始した[73]。貴族間の抗争と、ボスニア王国で迫害を受けていたボゴミル教徒の支持により、オスマン軍のボスニア進出は容易に進んだ[73]。オスマン軍はボスニア内に要塞を建設するとともに、農民に保護を与えて支持を得ていく[74]。ステファン・トマシェヴィッチはローマ教皇に宛てて、自国の窮状とメフメトがイタリア、ダルマチア、ハンガリーの征服を企てていることを訴える書簡を送った[74]。
1459年初秋、メフメトはギリシャ各地を訪問した[75]。歴史家ミカエル・クリトヴォロス(英語版)は、メフメトは廃墟や遺跡を見学し、住民が語るギリシャの歴史に耳を傾けたと伝えている[75]。また、1459年の初頭より、ペロポネソス半島では教皇庁と西ヨーロッパの援助を受けたソマスの指導による反乱が発生していた[76]。西ヨーロッパが反乱に加担していることを知ったメフメトは軍隊を派遣するが、モレアス側との交渉は失敗し、混乱はより拡大する[76]。
1460年5月にメフメトはペロポネソス半島に再び親征を行い、1461年春に遠征を終えて帰国する[77]。1461年7月に1年にわたってオスマン軍に頑強に抵抗していたサルモニコンが陥落したことでモレアス専制公国の征服が完了し、ペロポネソス半島の大部分がオスマンの支配下に入った[78]。ソマスはイタリアに逃亡し、オスマンに降伏したディミトリオスはメフメトから手厚い保護を受けた[79]。 1460年、アナトリア北部の東ローマ系国家トレビゾンド帝国の皇帝ダヴィドは、同盟国である白羊朝の力を頼みにして、毎年オスマンに支払う貢納金の免除を申し出た[62][80]。メフメトはこの要求に怒り、トレビゾンドを中心とするアナトリア北部の黒海沿岸部の征服を計画した[80]。1461年春、メフメトはモレアス遠征から帰国した数か月後に親征を開始する[78]。 行軍中、黒海に面する港湾都市スィノプを支配するペルヴァーネ侯国
トレビゾンド帝国の併合
ワラキアとの戦争19世紀にテオドール・アマンによって描かれたワラキア軍の夜襲
1459年にワラキアに課した貢納金を増額した際、ワラキア公ヴラド・ツェペシュは貢納金の支払いを拒否し、メフメトが詰問に向かわせた使者たちはヴラドによって処刑された[83]。1461年から1462年にかけての冬、オスマンの守備隊はテレオルマンでワラキア軍の攻撃を受けて敗北する。1462年にメフメトはワラキアに親征するが、ヴラドはゲリラ戦術を展開して抗戦した[84]。6月16日、メフメトの宿営はワラキア軍の夜襲によって大きな損害を受け(トゥルゴヴィシュテの夜襲)、6月中にメフメトはワラキアから撤退した[84]。同年夏、メフメトはヴラドの実弟であるラドゥ3世を指揮官とする遠征軍を新たにワラキアに派遣する。ワラキア国内の貴族の離反とハンガリーの妨害によってヴラドは失脚し、トランシルヴァニアに亡命したが、ハンガリー国王マーチャーシュ1世に逮捕されてブダに幽閉された[85]。
1462年にオスマン軍はヴェネツィア領のレスボス島を占領する。