Именно из этого динамичного английского порта в мае 1497 года отплыл Джон Кабот на трехмачтовой каравелле "Мэтью" под флагом Генриха VII. Себастьян Кабот утверждал, что он, тогда еще подросток, был на борту корабля в составе команды своего отца, состоявшей из восемнадцати человек. В июне они причалили к берегу, сошли на берег и обнаружили место для костра, палку, "вырезанную и раскрашенную бразильской краской", и тропу в лесу - все это говорило о том, что место было или есть обитаемым. Кабот и его люди установили крест, подняли знамя Генриха VII и штандарт Святого Марка Венецианского и вступили во владение этим местом от имени английского короля. Кабот назвал это место Prima Tierra Vista, или "Первая открытая земля". Где именно находилась эта земля, никто точно не знает. Одни говорят, что это Ньюфаундленд, другие - Новая Шотландия.
Когда Кэбот вернулся в Бристоль, его встретили с бурным восторгом, и он стал чем-то вроде знаменитости. "Он ходит одетый в шелк, - писал Лоренцо Паскуалиго, венецианский купец, живший в Лондоне, - и англичане бегают за ним как сумасшедшие". Кабот вполне мог заявить, что он достиг сказочного Катая. Паскуалиго сообщил, что "венецианец... который отправился на небольшом корабле из Бристоля на поиски новых островов", утверждает, что "открыл материк в 700 лигах отсюда, который является страной Великого Хана". Генрих VII был настолько восхищен, что наградил Кабота королевской пенсией и внушительным титулом: Великий адмирал.
Однако знаменитость не продлилась долго. В следующем году Кабот отправился в очередное плавание во главе флотилии из пяти кораблей, снова заручившись поддержкой Генриха и некоторых бристольских купцов. На это предприятие возлагались большие надежды. По словам посла герцога Миланского, планировалось "создать колонию", и, как он объяснил, "с помощью этого они надеются сделать Лондон более важным рынком пряностей, чем Александрия". Но Джон Кабот и его корабль так и не вернулись.
Существует предположение, что Себастьян отправился в это второе плавание, вернувшись в Англию на одном из кораблей, которые все же добрались до дома. Как бы то ни было, после смерти отца молодой венецианец унаследовал грамоту, выданную Генрихом VII, и через несколько лет, когда ему было уже за двадцать, отправился в путешествие через северную Атлантику. Отправившись в путь в 1508 году, Кабот увидел, как ему показалось, водный канал вокруг северного побережья Америки. По его мнению, это был путь в Катай - то, что стало известно как Северо-Западный проход. Вероятно, он достиг того места, которое сейчас называется Гудзоновым проливом, более чем за сто лет до его одноименного первооткрывателя Генри Гудзона. Позже Кабот рассказал, что он продолжил бы путь через пролив к Катаю, как он предполагал, если бы его команда не пригрозила мятежом и не убедила его вернуться в Англию. Когда Кабот вернулся домой, он обнаружил, что Генрих VII умер, а новый король, Генрих VIII, как сообщали венецианцы, "мало заботился о подобном предприятии" в Новом Свете.
В течение следующих трех лет после путешествия Кабот работал в Англии картографом. Затем, в 1512 году, он получил королевское разрешение отправиться в Испанию и работать на короля Фердинанда, тестя Генриха VIII. Похоже, его заманили туда перспективы "плавания в Индию и на остров Бакаллаос".* что означает Ньюфаундленд. Это долгожданное путешествие так и не состоялось, но Кабот, очевидно, произвел впечатление на испанский двор. В 1518 г. он получил выгодную должность лоцмана-майора в La Casa de la Contratación - Доме торговли - официальном органе, ответственном за управление практическими, политическими и экономическими вопросами, связанными с растущей испанской империей в Новом Свете. Лоцман-майор был, по сути, старшим навигатором страны - должность, созданная в 1508 году и впервые занятая Америго Веспуччи. В обязанности Кабота входило постоянное обновление "Падрона Реаль", главной карты морей мира, составленной Каса.