Безопасность от нападений венгров могла быть гарантирована только при условии полного контроля османов по линии Дунай — Сава, которая практически делит Балканы пополам от Черного моря на востоке до Адриатического — на западе. На северо-западе от Сербии и к югу от Савы расположена Босния, вассальное государство османов, чей король Стефан Томашевич также отказался посылать дань султану. В 1463 году Стефан просил о перемирии и получил его сроком на 15 лет, но практически немедленно османская армия напала на Боснию, войдя на ее территорию с юга. Стефан бежал, но Махмуд-паша нагнал его в Клуже, где он сдался, получив обещание, что его отпустят, не причинив вреда. Как и Сербия, Босния стала османской провинцией — хотя в следующем году вынуждена была защищаться от нападений Венгрии — и следующей Махмуд-паша захватил соседнюю Герцеговину. Коварство, позволившее османам напасть на Боснию несмотря на перемирие, снова проявилось, когда султан Мехмед приказал казнить Стефана Боснийского; но его захваченный единокровный брат Сигизмунд обратился в ислам и под именем Кралоглу («Сын короля») Исхак-бей стал соратником султана. Сын правителя Герцеговины также обратился в ислам и под именем Херсекзаде («Сын принца») Ахмед-паша служил великим визирем при сыне и наследнике Мехмеда Баязиде II (на дочери которого он женился) и его внуке Селиме I.
В 1455 году османы захватили генуэзские колонии на Эгейском море: Старую и Новую Фокайи (Фоча) на побережье Малой Азии к северу от Измира, контролировавшие богатые копи квасцов, продукция которых была необходима для европейской торговли тканями и использовалась для окраски; Энос (Энез), в устье Марицы во Фракии, получавший доходы от торговли солью. В том же году Афины были отвоеваны у их флорентийского правителя пограничным вождем Умур-беем, сыном Тупахан-паши. Венецианский Наксос и генуэзские острова Лесбос и Хиос согласились платить дань султану в 1458 году. После завоевания Сербии в 1459 году султан Мехмед возвратился в Стамбул, а затем по суше отправился покорять генуэзскую колонию Амастрис (Амасра) на черноморском побережье Малой Азии при поддержке военного флота, посланного из Стамбула. В 1462 году Лесбос капитулировал перед османской осадой, в то время как Мехмед строил укрепления на Дарданеллах, чтобы улучшить защищенность Стамбула. Он построил там две крепости, в Чанаккале, ранее известном как Султанхисар («Замок султана»), на малоазийском побережье, и в Килитюльбахре («Замок моря»), напротив первого, на побережье Румелии. Теперь, когда османы надежно контролировали южные подступы к Стамбулу, город был защищен от нападения с моря.
Даже после падения Константинополя сохранились несколько осколков Византийской империи. Эти анахроничные образования включали Трапезундскую империю Комнинов, ставшую османским вассалом в 1456 году, и деспотат Морею, совместно управлявшийся Фомой и Димитрием Палеологами. Будучи долгое время вассалом османов, деспотат в течение трех лет был не в состоянии выплачивать дань, пока армия султана Мехмеда не завоевала его в 1458 году. Выплата долга в последнюю минуту не смогла отклонить Мехмеда от его цели, и он двинулся на юг. Коринф сдался после трехмесячной осады, и османское управление распространилось на большую часть Пелопоннеса. Деспот Фома без особого энтузиазма попытался вернуть некоторые из своих бывших владений, но был втянут в войну со своим братом. В 1460 году Мехмед снова лично повел армию, которая к концу года покорила весь Пелопоннес, за исключением нескольких венецианских колоний, оставшихся под контролем османов. Греческие источники того времени сообщают, что дочь Димитрия Елена вошла в женскую половину семейства султана, его гарем, как и Тамара, дочь Георгия Франдзи, летописца правления Мехмеда.
Трапезунд был морским рынком сбыта дня торговли Тебриза, столицы Узун Хасана, энергичного лидера племенного союза Аккоюнлу, женатого на принцессе из дома Комнинов. Османские усилия подчинить мусульманские эмираты Малой Азии могли бы показаться несущественными по сравнению с разворачивавшейся в это время борьбой за контроль над восточной Малой Азией. Узун Хасан считал Трапезунд сферой своего влияния и в конце 1460 года отправил в качестве посланника к султану Мехмеду своего племянника, уведомляя, что считает империю своей добычей, и предупреждая султана, чтобы тот не пытался лишать права владения династию Комнинов. Мехмед проигнорировал предупреждение и при поддержке армий своих исламских вассалов Исфендиярогуллары Кастамону и Караманидов в следующем году двинулся на восток с целью захватить этот последний византийский анклав в Малой Азии, слишком маленький, чтобы называть себя империей. Узун Хасан послал войска остановить его наступление, но в первом противоборстве двух честолюбивых правителей успех не сопутствовал ни одной из сторон.