Арабские корабелы не использовали никаких рисунков или планов. Они строили суда исключительно «на глазок», руководствуясь лишь вековым опытом. В распоряжении Тима Северина имелись только рисунки арабских кораблей, приведённые на португальской морской карте Индийского океана, датируемой 1521 годом. Детали и подробности о размерах и мощности, скорости и особенностях конструкции можно было уточнить с помощью средневековых арабских текстов.
В поисках дальнейших сведений об арабском судостроении Тим Северин посетил султанат Оман. Расположенный у входа в Персидский залив, Оман имеет богатые морские традиции. Считается, что сам легендарный Синдбад был оманцем. Он родился в городе Сохар, некогда оживлённом порту на берегу Аравийского полуострова. Здесь, на побережье и в портах Омана, Тим Северин встретил нужные ему виды традиционных арабских кораблей и познакомился с местной судостроительной техникой. Очень доброжелательно отнеслись к его проекту сами оманцы, министерство национального наследия и культуры даже выступило в роли спонсора экспедиции.
Строить корабль Северин решил в городе Сур, на самом острие восточной оконечности Омана. Здесь в течение столетий арабские корабелы изготавливали купеческие суда, которые плавали от Занзибара на юге до Индии и Шри-Ланки на востоке в поисках древесины, специй и слоновой кости. Судно, названное «Сохар», — в честь города, где родился Синдбад, было заложено 1 января 1980 года. Длину корпуса определили в 26,5 метров. Двухмачтовый корабль с латинским парусным вооружением должен был нести три паруса: грот, бизань и кливер.
Найти стройматериалы для корабля оказалось поистине непосильной задачей. На Аравийском полуострове никакой корабельной древесины никогда не было. В Средние века арабы для постройки судов импортировали тик с Малабарского побережья Индии. Однако в 1979 году индийское правительство запретило экспорт тикового сырья. Пришлось заменить его очень схожей древесиной под названием айни — тоже индийского происхождения. Тим Северин семь раз побывал в лесах Западной Индии, организовывая заготовку подходящих деревьев. Брёвна были доставлены из джунглей на слонах и по морю отправлены в Сур.
Средневековые арабские суда сооружались без единого гвоздя — считалось, что гвозди и вообще железные крепления применять нельзя, потому что на морском дне якобы находятся огромные магниты, вытягивающие всё железо из проходящих кораблей. Поэтому арабские судостроители сшивали доски тонкими канатами из волокна кокосовой пальмы. Ещё совсем недавно в Омане встречались небольшие суда, построенные подобным образом, но технология их строительства была почти утрачена. Северину нужны были мастера, которые знали бы это древнее ремесло. Они нашлись лишь на острове Агатти, в отдалённом Лаккадивском архипелаге, примерно в 400 километрах от юго-западного побережья Индии. Их пригласили в Сур. На том же острове Северин закупил и 600 километров кокосового волокна. Примечательно, что арабы в средние века тоже плавали на Лаккадивские острова за кокосовыми верёвками.
Кроме специалистов по верёвочному ремеслу в Суре собрались и дюжина оманских корабелов, и группа индийских плотников с Малабарского побережья. Оманцы работали острыми, как бритва, топорами, вытёсывая шпангоуты. Индийцы предпочитали стамески из мягкого железа, которыми они вырезали замысловато изогнутые доски, а также делали сложные сцепки в огромных брусьях. Из единого ствола дерева они изготовили 20-метровую грот-мачту, и она выглядела так, словно была выточена на гигантском станке. Чтобы «сшить» корабль, потребовалось вручную просверлить около 20 тысяч отверстий, через которые должны были пройти кокосовые верёвки, связующие в единое целое всё судно. Изнутри дыры были заделаны скорлупой кокосовых орехов, а снаружи — смесью извести с сырым каучуком. Наконец, внутри корпус корабля был обработан швабрами, смоченными в растительном масле, чтобы предохранить от гниения кокосовое волокно и древесину. Оманские мастера заявили, что если регулярно пропитывать маслом корабль, то срок его службы может продлиться до 100 лет. А судно, построенное на гвоздях, через каждые десять лет должно проходить капитальный ремонт с заменой каждого гвоздя. Для лучшей сохранности в морской воде корпус ниже ватерлинии обрабатывался известью против корабельного червя, а также пропитывался рыбьим жиром.
Корабль был построен за 165 дней. В состав его экипажа вошли восемь оманцев, повар-белудж и десять европейцев. 23 ноября 1980 года «Сохар» поднял паруса и вышел в открытое море, держа курс на юго-восток.