Безопасность от нападений венгров могла быть гарантирована только при условии полного контроля османов по линии Дунай — Сава, которая практически делит Балканы пополам от Черного моря на востоке до Адриатического — на западе. На северо-западе от Сербии и к югу от Савы расположена Босния, вассальное государство османов, чей король Стефан Томашевич также отказался посылать дань султану. В 1463 году Стефан просил о перемирии и получил его сроком на 15 лет, но практически немедленно османская армия напала на Боснию, войдя на ее территорию с юга. Стефан бежал, но Махмуд-паша нагнал его в Клуже, где он сдался, получив обещание, что его отпустят, не причинив вреда. Как и Сербия, Босния стала османской провинцией — хотя в следующем году вынуждена была защищаться от нападений Венгрии — и следующей Махмуд-паша захватил соседнюю Герцеговину. Коварство, позволившее османам напасть на Боснию несмотря на перемирие, снова проявилось, когда султан Мехмед приказал казнить Стефана Боснийского; но его захваченный единокровный брат Сигизмунд обратился в ислам и под именем Кралоглу («Сын короля») Исхак-бей стал соратником султана. Сын правителя Герцеговины также обратился в ислам и под именем Херсекзаде («Сын принца») Ахмед-паша служил великим визирем при сыне и наследнике Мехмеда Баязиде II (на дочери которого он женился) и его внуке Селиме I.

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

Даже после падения Константинополя сохранились несколько осколков Византийской империи. Эти анахроничные образования включали Трапезундскую империю Комнинов, ставшую османским вассалом в 1456 году, и деспотат Морею, совместно управлявшийся Фомой и Димитрием Палеологами. Будучи долгое время вассалом османов, деспотат в течение трех лет был не в состоянии выплачивать дань, пока армия султана Мехмеда не завоевала его в 1458 году. Выплата долга в последнюю минуту не смогла отклонить Мехмеда от его цели, и он двинулся на юг. Коринф сдался после трехмесячной осады, и османское управление распространилось на большую часть Пелопоннеса. Деспот Фома без особого энтузиазма попытался вернуть некоторые из своих бывших владений, но был втянут в войну со своим братом. В 1460 году Мехмед снова лично повел армию, которая к концу года покорила весь Пелопоннес, за исключением нескольких венецианских колоний, оставшихся под контролем османов. Греческие источники того времени сообщают, что дочь Димитрия Елена вошла в женскую половину семейства султана, его гарем, как и Тамара, дочь Георгия Франдзи, летописца правления Мехмеда.

Трапезунд был морским рынком сбыта дня торговли Тебриза, столицы Узун Хасана, энергичного лидера племенного союза Аккоюнлу, женатого на принцессе из дома Комнинов. Османские усилия подчинить мусульманские эмираты Малой Азии могли бы показаться несущественными по сравнению с разворачивавшейся в это время борьбой за контроль над восточной Малой Азией. Узун Хасан считал Трапезунд сферой своего влияния и в конце 1460 года отправил в качестве посланника к султану Мехмеду своего племянника, уведомляя, что считает империю своей добычей, и предупреждая султана, чтобы тот не пытался лишать права владения династию Комнинов. Мехмед проигнорировал предупреждение и при поддержке армий своих исламских вассалов Исфендиярогуллары Кастамону и Караманидов в следующем году двинулся на восток с целью захватить этот последний византийский анклав в Малой Азии, слишком маленький, чтобы называть себя империей. Узун Хасан послал войска остановить его наступление, но в первом противоборстве двух честолюбивых правителей успех не сопутствовал ни одной из сторон.

Земли Комининов были отрезаны от внутренних районов Малой Азии высокими, суровыми горами. Янычар, служивший в османской армии в походе на Трапезунд, вспоминает трудности этой кампании: расстояние, враждебное отношение местного населения к продвижению османов в регионе, где крутые, покрытые лесом горы благоприятствовали скорее легким и подвижным, чем тяжеловооруженным воинам, голод и непрекращающийся дождь, который превращал дорогу в грязь. Он рассказывает, как нагруженный золотыми монетами верблюд упал на дорогу, ведущую к городу, рассыпав сокровища повсюду: султан Мехмед приказал всем, кто был в состоянии подобрать кусочки золота, оставить их себе. Но этого стимула было недостаточно:

Трапезунд сдался после шестидневной осады сухопутными и морскими силами османов. По исламскому закону тех, кто сдавался в бою, следовало отпустить, поэтому изначально императора и его семью пощадили и держали в Эдирне, кроме его дочери Анны, которая вошла в гарем Мехмеда, но казнили двумя годами позже. Некоторые обвиняли в легкой победе османов казначея Трапезунда Георгия Амируда, который вел переговоры о сдаче анклава с османским великим визирем Махмуд-пашой, приходившимся ему двоюродным братом. Амируц продолжил свою карьеру при османском дворе, как и некоторые другие образованные греки и византийские аристократы. Он стал придворным философом и личным секретарем султана; его особой заслугой было слияние воедино разрозненных карт античного греческого географа Птолемея, чей труд был принят за одну из основ исламской и, позднее, османской и европейской картографии. С устранением династии Комнинов из Трапезунда Мехмед завершил объединение под османской властью территорий, которые управлялись Византией из Константинополя до IV крестового похода в 1204 году.

Присоединение морских колоний Венеции все еще оставалось целью османов, поскольку, хотя Венеция и не была в состоянии представлять прямую стратегическую угрозу для османов после того, как они овладели Константинополем, она оставалась серьезной помехой, благодаря сильному флоту. Османо-венецианские отношения всегда омрачали взаимные подозрения, но полномасштабной войны обычно удавалось избежать. Из коммерческих соображений и будучи уверена в том, что остальные крестоносные державы, без сомнения оставят их в изоляции, Венеция не очень стремилась провоцировать османов, пока завоевание Боснии в 1463 году не поставило под уфозу венецианские владения на Адриатике. Другие венецианские колонии, в основном Корфу, Метони, Эвбея и Наксос, стали уязвимыми, когда османы напали на венецианские территории вокруг Нафпактоса (Лепанто), важной базы для осуществления морских операций в Адриатическом море. В надежде, что она сможет найти союзника в лице Венгрии, которой также угрожала потеря Боснии, Венеция объявила войну султану в июле 1463 года.