Пока высокопоставленные участники проекта хлопотали перед королем о предоставлении им особых привилегий в этом необычном деле, капитан Кидд с головой окунулся в решение назревших практических задач. С помощью Харрисона он укомплектовал команду «Эдвенчура» необходимым количеством моряков (набрали порядка 70 человек), после чего все участники предстоящего вояжа подписали «Правила соглашения». В этих «Правилах» отмечалось, что, оценив захваченную добычу, участники экспедиции должны были сначала вычесть все издержки, а затем уже делить оставшуюся часть между собой. Кидд имел право на 35 долей; другие офицеры тоже могли рассчитывать больше чем на одну долю. Полные доли получали опытные моряки, а «сухопутным крысам» и юнгам полагалось менее одной доли.
В конце февраля 1696 года все приготовления к плаванию были завершены. Кидд спешил, поскольку в столице ширились слухи о возможной скорой высадке на берегах Туманного Альбиона французского десанта. 23 февраля Адмиралтейство наложило эмбарго на все торговые суда и велело их шкиперам отдать королевскому флоту треть своих команд. 25-го числа того же месяца граф Белломонт отправил Кидду письмо с предписанием начать экспедицию.
Когда Кидд вывел свой фрегат из лабиринта лондонских доков и двинулся вниз по Темзе, ему пришлось пройти в районе Гринвича мимо упомянутой королевской яхты «Кэтрин». При этом он ничем не засвидетельствовал своего почтения военным морякам. С яхты прозвучал предупредительный выстрел, но и после этого «Эдвенчур» не приспустил свой флаг. Более того, члены его команды, решив покуражиться, выстроились вдоль борта, повернулись к королевской яхте спиной и продемонстрировали весьма грубый матросский «салют» — спустив штаны, они, по свидетельству таможенного досмотрщика Джеремайи Даммера, одновременно «шлепнули себя по задницам».
Разгневанный капитан яхты подал жалобу в морское ведомство. Лорды Адмиралтейства сначала отмахнулись от этой жалобы, однако, когда команда Кидда нанесла аналогичное оскорбление другому военному кораблю, их терпение лопнуло. Капитану Мандену было приказано задержать «Эдвенчур», забрать с него всех матросов, а само судно отвести на якорную стоянку в Ширнесс. Приказ был выполнен незамедлительно. Тридцать лучших матросов Кидда перевели на военный корабль «Дачис», капитаном которого был некто Стюарт. В распоряжении командира «Эдвенчура» осталось лишь 5 профессиональных моряков и 35 новобранцев.
Подобный поворот событий ставил экспедицию под угрозу срыва. Кидд немедленно послал одному из своих покровителей, адмиралу Расселу, просьбу о помощи. Прошло две недели, прежде чем Рассел смог вмешаться и исправить ситуацию. 20 марта он отдал приказ капитану Стюарту вернуть на галеру-фрегат рекрутированных матросов, что и было сделано. Сомнительно, однако, чтобы Кидд получил тех бравых парней, которых он самолично отобрал для экспедиции; скорее всего, ему прислали тех людей, от которых капитан «Дачиса» сам мечтал избавиться, — прощелыг и пропойц, подобранных в припортовых тавернах.
Пока опасность французского вторжения в Англию не миновала, «Эдвенчуру» пришлось вернуться назад, в Лондон, и там ждать, когда будет отменено эмбарго. Наконец, после девятнадцатидневной задержки, Кидд смог покинуть эстуарий Темзы и вывести свой корабль в открытое море. 10 апреля он стал на якорь в Даунсе, чтобы высадить на берег лоцмана, а затем отправился в Плимут.
В «Повествовании о путешествии капитана Уильяма Кидда, командира «Эдвенчур гэлли», из Лондона в Ост-Индию» (1699) сообщается, что «в 23-й день месяца апреля он отплыл из Плимута в назначенное ему плавание». Но путь его лежал не в южном, а в западном направлении. Прежде чем идти в Индийский океан, Кидд решил еще раз побывать в Нью-Йорке — во-первых, чтобы перед рискованным предприятием повидаться с женой и друзьями, а во-вторых, чтобы усилить свою команду волонтерами из североамериканских колоний.
Переход через Северную Атлантику оказался удачным. В конце мая, недалеко от Большой Ньюфаундлендской банки, англичане заметили французское рыболовное судно. Его настигли, выстрелили из погонной пушки, требуя остановиться, после чего без боя взяли в качестве трофея. На борту приза обнаружили четырех рыбаков и типичный для такого рода судов груз — соль и рыболовное снаряжение. Всё это можно было продать в Нью-Йорке, а на вырученные деньги купить провизию для предстоящего плавания на Восток.
В начале июля, подгоняемый легким бризом, «Эдвенчур» появился у Лонг-Айленда. Впередсмотрящий, высунувшись из «вороньего гнезда», пропел традиционное «Земля на горизонте!», и вскоре пушечный выстрел возвестил о прибытии корабля на нью-йоркский рейд.