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