Даже выполняя свои официальные обязанности, Кабот сохранял интерес к поиску северного прохода на Восток. В 1519 году к Каботу - хотя теперь он был испанским чиновником - обратился английский кардинал Томас Вулси, влиятельный советник Генриха VIII, с просьбой возглавить "путешествие с целью открытия" на "новооткрытый остров" ради "чести" Генриха и "для общего богатства его королевства". Неизвестно, чем был вызван внезапный интерес Генриха к Новому Свету, но он пообещал предоставить корабли для этого предприятия, если купцы оплатят поставки и зарплату морякам. В обмен на их поддержку Генрих обещал предоставить монополию на торговлю на десять лет и пятнадцатимесячное освобождение от уплаты таможенных пошлин.
Купцы рассмотрели это предложение. Три брата Грешэм - Уильям, Ричард и Джон - согласились вложить деньги, как и другие члены Мерсеров и некоторые бристольские купцы. Однако большинство лондонских купцов не были убеждены. Особенно сомневались члены Worshipful Company of Drapers, влиятельной гильдии торговцев тканями, утверждавшие, что нет смысла рисковать жизнями людей и товарами ради "исключительного доверия одного человека", а именно Себастьяна Кабота. Они ставили под сомнение его опыт и сомневались в его утверждениях, полагая, что он просто повторяет то, что "слышал от своего отца и других людей в прошлые времена". Хотя Генрих пытался сохранить миссию, в конце концов, в 1521 году она распалась.
Потеряв надежду, Кабот, которому уже подходило к сорока, продолжил работу в Испании в качестве лоцмана-майора "Ла Каса". Затем, в 1524 году, появилась еще одна возможность, на этот раз благодаря Карлу V, правителю Испанской империи. Консорциум купцов, включая Роберта Торна, английского торговца из Севильи, чей отец спонсировал Джона Кэбота, согласился финансировать путешествие на Восток с Себастьяном во главе. Карл поручил Каботу наполнить его корабли "всем золотом, серебром, жемчугом, драгоценными камнями, лекарствами и пряностями", которые можно было найти в "восточном Китае, Таршише, Офире, Японии, на островах Молуккских и других землях и островах".
В апреле 1526 года флот Кабота отправился через Атлантику. Ему было поручено пройти через Магелланов пролив, названный так в честь португальского дворянина Фердинанда Магеллана, который пятью годами ранее открыл проход вокруг южной оконечности Южной Америки, совершив первое кругосветное путешествие. Но Каботу не удалось достичь пролива, и когда он вернулся в Испанию, его арестовали, судили, осудили и приговорили к ссылке в Оран, торговый город на северном побережье Африки, ныне Алжир, контролируемый испанцами.
Однако в конце концов он был оправдан и восстановлен в должности майора-пилота.
Насколько много ДЖОН ДАДЛИ знал о деталях этого бурного эпизода из прошлого Себастьяна Кабота в Испании, неизвестно, но он считал, что, какими бы ни были его недостатки, венецианец был человеком с исключительным опытом, знаниями и упорством.
Не было никаких гарантий, что Кэбот решит вернуться в Англию. Он построил свою жизнь в Испании, и, несмотря на пятно на его репутации, Карл V по-прежнему высоко ценил его. Но на работе все было не так радужно. В Ла-Касе Кабот оказался втянутым в политическую игру, поскольку между сторонниками практических и теоретических аспектов навигации разгорелся ожесточенный спор. Кэбот был практиком и с подозрением относился к академическим теоретикам, но он проигрывал дебаты, а вместе с ними и свой авторитет лидера "Ла Каса".
В свои шестьдесят с лишним лет он мог бы продолжать жить, довольствуясь достойной пенсией. Но в 1547 году умерла его любимая жена-испанка, и внезапно у него не осталось родственных связей, которые могли бы удержать его в Испании. Вскоре он попросил шестимесячный отпуск от своих обязанностей в Ла-Касе, заявив, что намерен посетить Брюссель, где ему необходимо заняться некоторыми деловыми вопросами. Именно тогда Дадли, зная, что Кэботу грозит неопределенное будущее и он собирается покинуть Испанию, воспользовался своим шансом. Он и его коллеги по тайному совету выделили сто фунтов "на перевозку одного Кабота, лоцмана, чтобы он вышел из Испанской империи, чтобы служить и жить в Англии". К следующему году Кабот был в Англии, и его наградой стало вознаграждение в размере 166 фунтов стерлингов.
Карл был в ярости из-за отъезда Кабота. В апреле 1549 года он поручил своему послу потребовать возвращения Кабота, позже объяснив, что венецианец "должен четко понимать, что мы нуждаемся в его услугах и требуем права на них". Но Кабот успешно уклонился от этих требований, вскоре доказав, что Чарльз был прав, когда сердился. После прибытия в Англию Кабот участвовал в планировании более чем одного смелого зарубежного проекта, вероятно, по указанию Дадли. Одним из них было нападение на Перу, источник серебряных богатств Испании, но оно не осуществилось. Второй - путешествие в Катай, которое рассматривали английские купцы. Как отметил посол Испании, "жители Лондона высоко ценят услуги капитана и считают, что он владеет секретами английской навигации".