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

Совместные османо-татарские действия против генуэзцев были предшественниками их будущих близких, а зачастую и непростых отношений. Татарская династия Гирея, правившая Крымом до его завоевания Российской империей в конце XVIII века, появилась в XV веке, провозгласив свою независимость от татар Золотой Орды, которые контролировали западную часть Монгольской империи, созданной Чингиз-ханом, и были призваны занять особое место в османской истории. Гирей возводил свою генеалогию к Чингиз-хану и поэтому мог претендовать на что-то вроде политической законности, о которой османы могли только мечтать: верховенство татар в неофициальной иерархии центрально-азиатских династий давало им небывалый авторитет среди мусульманских государств и приносило немало беспокойства османам.

В течение первых 10 лет после «Завоевания» султан Мехмед сосредоточил свое внимание почти исключительно на Балканах. Его первый большой поход после 1453 года был против Сербии – буфера между османами и венгерской территорией, а также маршрутом, по которому венгерское влияние могло проникнуть на Балканы, а венгерские армии угрожать его северо-западным границам. Завоевание Сербии и ее окончательное включение в империю Мехмеда заняло пять лет. Хотя османы захватили и короткое время удерживали пару сербских крепостей в долине реки Моравы в 1454 году, они не смогли взять Смедерево, важную крепость, охранявшую направление на Дунай к востоку от Белграда. В последующие годы цель кампании была совсем другой: османская армия двинулась через юг Сербии в богатый залежами серебра район Ново Брдо, обеспечив себя ценнейшим природным ресурсом, залежи которого на их территории были ограничены. В 1456 году Мехмед командовал осадой Белграда, крепости, стратегическое положение которой при слиянии рек Дуная и Савы делало ее ключом к Венгрии: он не смог взять ее в ходе комбинированной операции на суше и на воде из-за неприступной и хорошо укрепленной позиции, а не из-за многочисленной, но разношерстной, плохо организованной армии крестоносцев, пришедшей на помощь крепости. Она оставалась в руках Венгрии до 1522 года.

Янош Хуньяди умер от чумы вскоре после осады Белграда, но его мужественная защита замка снискала ему славу героя легенды в венгерской истории. За его смертью последовал период смут; в конечном итоге в 1458 году трон унаследовал его сын Матиаш Корвин. Деспот Сербии Георгий Бранкович умер в декабре 1456 года; его сын Лазарь вскоре последовал за отцом, не оставив потомков мужского пола. Образовался вакуум власти, способствовавший османскому нашествию на Венгрию. Впервые Сербия стала османским вассалом после битвы на Косовом поле 1389 года, но в то время как ее правители проводили осторожную политику в отношении своих хозяев, для большинства православной знати османское правление было предпочтительнее правления католической Венгрии.