Присоединение морских колоний Венеции все еще оставалось целью османов, поскольку, хотя Венеция и не была в состоянии представлять прямую стратегическую угрозу для османов после того, как они овладели Константинополем, она оставалась серьезной помехой благодаря сильному флоту. Османо-венецианские отношения всегда омрачались взаимными подозрениями, но полномасштабной войны обычно удавалось избежать. Из коммерческих соображений и будучи уверенной в том, что остальные крестоносные державы, без сомнения, оставят их в изоляции, Венеция не очень стремилась провоцировать османов, пока завоевание Боснии в 1463 году не поставило под угрозу венецианские владения на Адриатике. Другие венецианские колонии, в основном Корфу, Метони, Эвбея и Наксос, стали уязвимыми, когда османы напали на венецианские территории вокруг Нафпактоса (Лепанто), важной базы для осуществления морских операций в Адриатическом море. В надежде, что она сможет найти союзника в лице Венгрии, которой также угрожала потеря Боснии, Венеция объявила войну султану в июле 1463 года.

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

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

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