Безрезультатная война османов с мамлюками уже закончилась, когда в 1495 году умер Джем, и Баязид мог теперь обратить свое внимание на Запад. Венецианский посол в Стамбуле увидел широкие приготовления, проводившиеся в арсенале в бухте Золотой Рог в 1499 году, но не мог предположить, что целью может быть его республика или ее приморские территории: Венеция проявляла осторожность, держась подальше от любых планов крестового похода, обсуждавшихся в годы плена Джема, и жила в мире с османами с 1479 года. Вместо этого он подумал, как и рыцари-госпитальеры, что армада будет направлена к острову Родос.

Похоже, что Баязид стремился завершить план отца по изгнанию венецианцев из остававшихся у них аванпостов. Нафпактос сдался после наступления с моря и с суши 28 августа 1499 года, и османы укрепили защиту узкого входа в Коринфский залив двумя стоящими друг против друга крепостями – таким же образом они укрепили защиту других своих стратегических фарватеров, Босфора и Дарданелл. Сама Венеция была потрясена в октябре вылазками, проникшими на ее территорию вглубь на 30 километров. В начале 1500 года венецианский эмиссар добивался возвращения Нафпактоса на аудиенции при османском дворе, но его поставили в известность, что султан собирается завладеть всеми венецианскими аванпостами на восточном побережье Адриатического моря и сделать Адриатику границей между его владениями и Венецией; позже в этом году Модон, Корон и Пилос (Наварино) на побережье юго-западной части Пелопоннеса были взяты в результате нападения османов с моря.

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

Победу в войне с Венецией принесли Баязиду морские силы, но они нуждались в восстановлении, и он приступил к полномасштабной реконструкции своего флота. Были построены более легкие, более маневренные корабли, личный состав флота значительно увеличился. В течение нескольких лет не совершалось никаких серьезных морских операций, флот был задействован для удерживания морских путей открытыми, защищая торговые и другие суда от пиратства, как свои, так и иностранные, ходившие в восточных водах Средиземного моря.

Наличие мощного флота открыло для османов новые перспективы, как когда-то для европейских государств. После того как Васко да Гама обогнул мыс Доброй Надежды в ноябре 1497 года и добрался до Индии следующей весной, коммерческие интересы Португалии вошли в конфликт с многовековой арабской торговлей в Индийском океане; в частности, они угрожали контролю мамлюков над торговлей специями из Южной и Юго-Восточной Азии. Усилия мамлюков на море оказались недостаточными, чтобы защитить свои интересы: в том же году, когда португальцы активизировались в Индийском океане, в восточной части Средиземного моря стало расти число пиратских нападений с острова Родос, и победа родосского флота над мамлюкским конвоем с грузом дерева с берегов Северной Сирии в 1508 году продемонстрировала беспомощность мамлюков на море. Мамлюкам пришлось обратиться за помощью к Баязиду, таким образом Баязиду удалось добиться того, чего он не смог взять силой: признания его превосходства над мамлюками в борьбе за господство на Ближнем Востоке. В 1510 году посольство к османскому двору было вознаграждено дополнительной помощью оружием и продовольствием для мамлюкского флота. В дополнение к компетентности в морском деле, артиллерия османов была не хуже, чем та, которую использовали европейцы; они снабдили флот мамлюков пушками против португальцев, а также отправили своих офицеров командовать мамлюкским флотом.