Трапезунд был морским рынком сбыта дня торговли Тебриза, столицы Узун Хасана, энергичного лидера племенного союза Аккоюнлу, женатого на принцессе из дома Комнинов. Османские усилия подчинить мусульманские эмираты Малой Азии могли бы показаться несущественными по сравнению с разворачивавшейся в это время борьбой за контроль над восточной Малой Азией. Узун Хасан считал Трапезунд сферой своего влияния и в конце 1460 года отправил в качестве посланника к султану Мехмеду своего племянника, уведомляя, что считает империю своей добычей, и предупреждая султана, чтобы тот не пытался лишать права владения династию Комнинов. Мехмед проигнорировал предупреждение и при поддержке армий своих исламских вассалов Исфендиярогуллары Кастамону и Караманидов в следующем году двинулся на восток с целью захватить этот последний византийский анклав в Малой Азии, слишком маленький, чтобы называть себя империей. Узун Хасан послал войска остановить его наступление, но в первом противоборстве двух честолюбивых правителей успех не сопутствовал ни одной из сторон.
Земли Комининов были отрезаны от внутренних районов Малой Азии высокими, суровыми горами. Янычар, служивший в османской армии в походе на Трапезунд, вспоминает трудности этой кампании: расстояние, враждебное отношение местного населения к продвижению османов в регионе, где крутые, покрытые лесом горы благоприятствовали скорее легким и подвижным, чем тяжеловооруженным воинам, голод и непрекращающийся дождь, который превращал дорогу в грязь. Он рассказывает, как нагруженный золотыми монетами верблюд упал на дорогу, ведущую к городу, рассыпав сокровища повсюду: султан Мехмед приказал всем, кто был в состоянии подобрать кусочки золота, оставить их себе. Но этого стимула было недостаточно:
…прежде чем мы спустились с горы, у нас было много злоключений: земля была вязкой как каша, и янычары были вынуждены нести императора [т. е. султана] на руках в течение всего пути в долину, а нагруженные сокровищами верблюды остались в горах. Император Мехмед умолял янычар попытаться спустить верблюдов в долину, и мы должны были с большим трудом подняться обратно в гору и бились всю ночь, прежде чем спустили их в долину. В тот день император остановился на отдых и отдал янычарам 50 000 золотых слитков, чтобы они разделили их между собой, и повысил жалование центурионов янычар.
Трапезунд сдался после шестидневной осады сухопутными и морскими силами османов. По исламскому закону тех, кто сдавался в бою, следовало отпустить, поэтому изначально императора и его семью пощадили и держали в Эдирне, кроме его дочери Анны, которая вошла в гарем Мехмеда, но казнили двумя годами позже. Некоторые обвиняли в легкой победе османов казначея Трапезунда Георгия Амируда, который вел переговоры о сдаче анклава с османским великим визирем Махмуд-пашой, приходившимся ему двоюродным братом. Амируц продолжил свою карьеру при османском дворе, как и некоторые другие образованные греки и византийские аристократы. Он стал придворным философом и личным секретарем султана; его особой заслугой было слияние воедино разрозненных карт античного греческого географа Птолемея, чей труд был принят за одну из основ исламской и, позднее, османской и европейской картографии. С устранением династии Комнинов из Трапезунда Мехмед завершил объединение под османской властью территорий, которые управлялись Византией из Константинополя до IV крестового похода в 1204 году.
Присоединение морских колоний Венеции все еще оставалось целью османов, поскольку, хотя Венеция и не была в состоянии представлять прямую стратегическую угрозу для османов после того, как они овладели Константинополем, она оставалась серьезной помехой, благодаря сильному флоту. Османо-венецианские отношения всегда омрачали взаимные подозрения, но полномасштабной войны обычно удавалось избежать. Из коммерческих соображений и будучи уверена в том, что остальные крестоносные державы, без сомнения оставят их в изоляции, Венеция не очень стремилась провоцировать османов, пока завоевание Боснии в 1463 году не поставило под уфозу венецианские владения на Адриатике. Другие венецианские колонии, в основном Корфу, Метони, Эвбея и Наксос, стали уязвимыми, когда османы напали на венецианские территории вокруг Нафпактоса (Лепанто), важной базы для осуществления морских операций в Адриатическом море. В надежде, что она сможет найти союзника в лице Венгрии, которой также угрожала потеря Боснии, Венеция объявила войну султану в июле 1463 года.
На ранней стадии войны большая часть Пелопоннеса снова перешла под венецианский контроль. Осенью 1463 года король Венгрии Матиаш Корвин захватил Боснию, а в следующем году его войско разбило армию под командованием Мехмеда, который отступил, узнав, что король снова движется на юг за реку Саву. Папа и герцог Бургундский заключили трехлетнее соглашение о крестовом походе против османов (но это рискованное начинание оказалось недолговечным: к концу 1464 года этот, как и многие другие союзы в истории крестовых походов, распался в результате разногласий).
Хотя венецианцы не смогли отбить у османов остров Лесбос на севере Эгейского моря в том же году, к этому отнеслись как простой неудаче, и Венеция склонялась к тому, чтобы принять мирные предложения верховного визиря Махмуд-паши.
Венеция оставалась проблемой, и не только на Пелопоннесе. Между османской Македонией и венецианскими крепостями на Адриатическом побережье лежал островок независимой Албании Скандербега. После того как Скандербег повторно принял христианство и отказался от клятвы османам, восстав против Мурада II, он добивался латинского покровительства в своем стремлении оставаться независимым от захватчиков-османов. Неаполь был его покровителем с 1451 года, но после смерти короля Альфонсо в 1458 году он снова признал османский суверенитет. Начало венецианско-османской войны в 1463 году дало ему еще один шанс освободиться от османов, и он предложил свои услуги Венеции. После двух лет локальных военных действий Мехмед начал полномасштабную кампанию против Скандербега, и летом 1466 года, всего за 25 дней, османы построили грандиозную крепость Эльбасан в том месте, где основной путь, связывающий османские Балканы с Адриатическим побережьем, бывшая Виа Игнатия, достигает прибрежной равнины. Крепость Скандербега Круя осталась отрезанной, будучи не в состоянии установить контакт по суше с венецианскими силами на побережье. В течение зимы Скандербег искал помощи в Италии, и в следующем году атаковал османов, осаждавших Крую. Это подтолкнуло Мехмеда ко второму наступлению, закончившемуся тем, что вся Албания, за исключением нескольких венецианских сторожевых застав, перешла под господство османов. Сам Скандербег, бывший такое долгое время лидером албанского сопротивления османам, бежал на венецианскую территорию, где умер в 1468 году. Хотя османское управление в этом недружелюбном регионе оставалось слабым, Венгрия и Венеция были более не в состоянии использовать в своих целях непостоянство мелких албанских властителей.
Хотя Мехмед II воспринимается западными историками в основном как автор броска османов в Европу, изрядную часть своего правления он защищал свои восточные границы. Предостережение Мехмеда Узун Хасаном по поводу Трапезунда в 1460 году оказалось пророчеством более агрессивной политики, поскольку вскоре он отправил посла в Венецию с предложением сотрудничества. Самой сильной картой в его колоде было обещание повторить успех Тамерлана и разделить османские владения: Венеция согласилась с тем, что он будет вправе оставить за собой любые территории, которые сможет завоевать в Малой Азии.
К середине XV века давние и непростые отношения между государствами Османов и Караманидов зашли в тупик. Смерть в 1464 году вассала Мехмеда правителя Карамана Ибрахим-бея оставила Караман открытым для соперничающих притязаний османов и Аккоюнлу. Узун Хасан не упустил шанса перехватить инициативу у османов, вторгнувшись в Караман от имени старшего сына Ибрахима Исхака и передав государство ему. И Узун Хасан и Исхак приняли покровительство мамлюков, надеясь на союз против неизбежного ответа Мехмеда, которого не пришлось долго ждать: при поддержке османов другой сын Ибрахима Пир Ахмед вынудил Исхака искать убежища у Узун Хасана. Смерть Исхака вскоре после этого лишила Узун Хасана предлога для вторжения в Караман и на время отложила исполнение его замысла превзойти Тамерлана.
Тем не менее вскоре, когда лучшие силы османской армии были заняты на западных границах империи, Узун Хасан на восточной границе добавлял большие полосы территории к тому, что он получил в результате присоединения земель вражеского племенного союза Каракоюнлу в 1467 году. В последующие два года он установил свою власть в Азербайджане, Ираке, Фарсе, Кирмане и за их пределами, на родине Тимуридов дальше на восток, что радикально изменило положение сил в восточной части Малой Азии и сделало Узун Хасана значительно более серьезным соперником, чем когда он был просто племенным вождем.
