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