Согласно приказу о плавании, корабли должны были двигаться к устью Темзы, что составляло около тридцати пяти миль. Там они должны были повернуть на север в Северное море, Mare Germanicus, а затем направиться к Oceanus Deucale - ныне известному как Норвежское море - которое лежит за Шотландией.
Пройдя норвежское побережье, они должны были снова повернуть на восток и продолжить плавание, насколько позволит ветер и море. Если все пойдет хорошо, они пройдут по северо-восточному морскому пути, обогнут территорию, обозначенную на карте Кабота как Terra Incognita - Неизвестная земля, и достигнут искомого выхода в Китайское море. Оттуда они каким-то образом доберутся до Катая и восточных рынков, где обменяют английские ткани на пряности и шелка, а затем проделают все в обратном порядке.
Это была смелая стратегия "голубого океана" в самом буквальном смысле слова. Для осуществления этого плана Уиллоуби и Ченселлор собрали команду из 116 человек - разумеется, моряков, а также поваров, плотников, кухарок, артиллеристов, хирургов и министра. На борту также находился большой контингент купцов - восемнадцать человек, которые должны были стать первыми английскими коммерсантами, осваивающими новые заморские рынки.
В Рэтклиффе их провожал Себастьян Кэбот. Сейчас ему было около семидесяти, его роскошные волосы совсем поседели, а борода, раздвоенная на кустистые локоны, доходила до груди. Он был слишком стар, чтобы самому совершить путешествие, но, тем не менее, оно оставалось воплощением мечты всей его жизни: доказать существование северного прохода в Катай.
В тот майский день, когда прилив отступил, мореплаватели, блиставшие в своих лазурно-голубых нарядах, сшитых из ткани, произведенной в крошечной рыбацкой деревушке Уотчет на юго-западном побережье Англии, попрощались со своими женами и детьми, родственниками и друзьями, собравшимися, чтобы проводить их.7 Затем корабли двинулись вниз по течению к Дептфорду, где встали на якорь на ночь. На второй день флот приблизился к Гринвичу и роскошному дворцу на берегу реки, где в то время находилась резиденция Эдуарда и его двора. При виде приближающихся кораблей придворные выбежали из дворца, чтобы посмотреть, как они проплывают мимо. Горожане стекались к берегу реки, чтобы помахать рукой. Члены Тайного совета выглядывали из окон своих покоев. Другие вскарабкались на вершины башен, чтобы полюбоваться происходящим. Матросы кричали, карабкались по такелажу, взбирались на палубу, подпрыгивали на лонжеронах и стреляли из корабельных пушек так, что "вершины холмов звучали от этого". Шествие, по словам очевидца, было "очень триумфальным". За исключением одного момента. Молодой король был серьезно болен и не мог подойти к окну. Присутствующие опасались за его жизнь.
Шесть дней флот Уиллоуби плыл по Темзе, преодолевая потоки и течения от Блэкуолла до Вулвича и Грейвсенда, пока не достиг выхода в Северное море. Затем они поплыли вдоль восточного побережья Англии, зайдя в порт Харидж, расположенный примерно в пятидесяти милях к северу от устья Темзы, где ждали благоприятного ветра. Наконец в конце июня подул попутный ветер с юго-запада, и "Бона Эсперанса", "Бона Конфиденция" и "Эдвард Бонавентура" "ушли в море, отдавая последнее прощание родной стране, которую они не знали, вернутся ли когда-нибудь снова увидеть". Не зная, "какие опасности их ожидают" или "какие неопределенности моря им предстоит испытать", мореплаватели, как сообщается, "часто оглядывались назад и не могли удержаться от слез". Даже Ричард Ченселлор, каким бы мужественным он ни был, выглядел "несколько обеспокоенным", потому что "оставил позади себя двух маленьких сыновей", которые "останутся сиротами, если он не поправится".
Флот Уиллоугби следовал указаниям Кэбота так точно, как только мог, и сумел проплыть "в компании" - вместе, как он и указал. В конце июля, после более чем месячного пребывания в море, у берегов Норвегии разразился сильный шторм. "Из-за сильного ветра и густого тумана, - записал Уиллоуби в своем вахтенном журнале, - мы не могли держаться вместе в пределах видимости". Канцлер опасался, что его товарищи потеряны не только для него, но и для всего мира: "Если ярость и гнев моря поглотили этих хороших людей, или если они еще живут и скитаются по чужим странам, я должен сказать, что они были людьми, достойными лучшей судьбы".