На ранней стадии войны большая часть Пелопоннеса снова перешла под венецианский контроль. Осенью 1463 года король Венгрии Матиаш Корвин захватил Боснию, а в следующем году его войско разбило армию под командованием Мехмеда, который отступил, узнав, что король снова движется на юг за реку Саву. Папа и герцог Бургундский заключили трехлетнее соглашение о крестовом походе против османов (но это рискованное начинание оказалось недолговечным: к концу 1464 года этот, как и многие другие союзы в истории крестовых походов, распался в результате разногласий).

Хотя венецианцы не смогли отбить у османов остров Лесбос на севере Эгейского моря в том же году, к этому отнеслись как простой неудаче, и Венеция склонялась к тому, чтобы принять мирные предложения верховного визиря Махмуд-паши.

Венеция оставалась проблемой, и не только на Пелопоннесе. Между османской Македонией и венецианскими крепостями на Адриатическом побережье лежал островок независимой Албании Скандербега. После того как Скандербег повторно принял христианство и отказался от клятвы османам, восстав против Мурада II, он добивался латинского покровительства в своем стремлении оставаться независимым от захватчиков-османов. Неаполь был его покровителем с 1451 года, но после смерти короля Альфонсо в 1458 году он снова признал османский суверенитет. Начало венецианско-османской войны в 1463 году дало ему еще один шанс освободиться от османов, и он предложил свои услуги Венеции. После двух лет локальных военных действий Мехмед начал полномасштабную кампанию против Скандербега, и летом 1466 года, всего за 25 дней, османы построили грандиозную крепость Эльбасан в том месте, где основной путь, связывающий османские Балканы с Адриатическим побережьем, бывшая Виа Игнатия, достигает прибрежной равнины. Крепость Скандербега Круя осталась отрезанной, будучи не в состоянии установить контакт по суше с венецианскими силами на побережье. В течение зимы Скандербег искал помощи в Италии, и в следующем году атаковал османов, осаждавших Крую. Это подтолкнуло Мехмеда ко второму наступлению, закончившемуся тем, что вся Албания, за исключением нескольких венецианских сторожевых застав, перешла под господство османов. Сам Скандербег, бывший такое долгое время лидером албанского сопротивления османам, бежал на венецианскую территорию, где умер в 1468 году. Хотя османское управление в этом недружелюбном регионе оставалось слабым, Венгрия и Венеция были более не в состоянии использовать в своих целях непостоянство мелких албанских властителей.

Хотя Мехмед II воспринимается западными историками в основном как автор броска османов в Европу, изрядную часть своего правления он защищал свои восточные границы. Предостережение Мехмеда Узун Хасаном по поводу Трапезунда в 1460 году оказалось пророчеством более агрессивной политики, поскольку вскоре он отправил посла в Венецию с предложением сотрудничества. Самой сильной картой в его колоде было обещание повторить успех Тамерлана и разделить османские владения: Венеция согласилась с тем, что он будет вправе оставить за собой любые территории, которые сможет завоевать в Малой Азии.

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

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

В 1468 году Узун Хасан отправил посольство к новому султану малюков Вахид-бею, чтобы заручиться поддержкой мамлюков против османов. Два писателя того времени, венецианский историк Доменико Малипьеро и османский Турсун-бей, сообщают независимо друг от друга о планах отправиться в поход на мамлюкскую Сирию. Тем не менее когда караманский Пир Ахмед не предоставил обязательную помощь этой кампании, Мехмед направил свою армию против Карамана. Неизвестно, что побудило Пир Ахмеда принять такое ошибочное решение, поскольку силы Карамана не могли соперничать с армией Мехмеда, который успешно взял большую часть территории Карамнидов к северу от горного хребта Тавр под свой контроль. Узун Хасан был поглощен своими собственными имперскими замыслами на востоке и не смог вмешаться, чтобы помочь Пир Ахмеду.

С 1469 года, после завоевания земель тимуридского правителя Абу Саида, Узун Хан стал владыкой самых обширных территорий в регионе, наследником Каракоюнлу и государства Тимуридов. Поскольку владения Узун Хасана включали большую часть Ирана и Ирака, а также изрядную часть Малой Азии, он был хозяином империи, соперничающей с империей султана Мехмеда, и в июне того же года он озвучил свои требования на то, чтобы быть единственным легитимным повелителем мусульман в послании к Вахид-бею. Это был вызов как мамлюкам, хранителям мусульманских святынь в Мекке и Медине, к которым всем мусульманам предписывалось совершить паломничество, так и стремлению султана Мехмеда стать лидером мусульманского мира. Даже после завоевания Константинополя Мехмед был за то, чтобы оставить вопросы, связанные с паломничеством, мамлюкам, считая своей обязанностью расширять мусульманские земли в настоящей жизни.

Узун Хасан усилил давление. Он соперничал с Мехмедом как на духовном, так и на светском уровне, говоря в письме к султану в 1471 году о своем недавнем завоевании Шираза в Южном Иране как о «троне халифата». Эта претензия не очень обеспокоила Мехмеда, поскольку права халифа уже давно были неопределенными, но воскрешение Узун Хасаном в памяти призрака Тамерлана тревожило больше. Один из военачальников Узун Хасана написал османскому губернатору Сиваса, проводя сравнение между лидером Аккоюнлу и Тамерланом — он считал Узун Хасана выше по 14 пунктам, которые включали полный набор атрибутов, необходимых для поддержания претензий правителя на легитимность в этой части мира. Узун Хасан привлек к себе интерес, критикуя политические решения османов, такие как взимание с мусульманских соплеменников подушного налога, который должны были платить только немусульмане, насильственное прикрепление племен к земле, чтобы сделать их частью оседлого крестьянства, что было важным аспектом османской политики подчинения восточной Малой Азии. Претензии Узун Хасана на происхождение от древних тюрок были решительным противопоставлением османам, делавшим акцент на свое центрально-азиатское происхождение.