Точных сведений о Сюй Фу не сохранилось. Имя его известно лишь из легенд жителей провинции Кии. По легенде Сюй Фу был выдающимся даосским мудрецом, магом и служил придворным лекарем китайского императора Цинь Шихуанди (246-210 гг. до н.э.). Шихуанди славился своей половой распущенностью и общей неумеренностью. Он очень любил свою сладкую жизнь, страшно боялся смерти и поэтому приблизил к себе большую группу даосских мудрецов, активно занимавшихся поиском эликсира бессмертия, надеясь с их помощью сохранить вечную молодость. Одним из этих мудрецов и был Сюй Фу.
   Однажды Шихуанди прослышал от даосов, что в восточном море расположен остров, где якобы растут волшебные деревья, дающие плоды, возвращающие молодость и наделяющие бессмертием. Он тут же распорядился снарядить экспедицию на поиски загадочного острова и назначил ее руководителем Сюй Фу.
   После нескольких месяцев плавания китайские моряки наконец увидели землю. Только оказался это не волшебный остров, а японская земля Кии. Туземцы радушно встретили пришельцев и оказали им всемерную помощь в поиске чудодейственных плодов. Однако, обрыскав все окрестности, китайцы их так и не нашли. Экспедиция провалилась, а у Сюй Фу появилось горячее желание навсегда остаться в этих гостеприимных краях: Цинь Шихуанди ошибок не прощал, и возвращение в Китай без волшебных плодов было равнозначно самоубийству. Поэтому Сюй Фу принял японское имя Оюротаюя и при помощи даосской магии стал государем земли Кии.
   Как видим, в легенде не сообщается о том, что Сюй Фу передал островитянам какие-либо методы шпионажа или ведения боевых действий. Не упоминается также, был ли он вообще с ними знаком. Нет здесь и описаний каких-либо «ниндзеподобных акций». И все же одного того, что Сюй Фу владел приемами магии оказалось достаточным, чтобы «по сходству» произвести его в «отцы-прародители» нин-дзюцу.
   Известный японский исследователь Окусэ Хэйситиро отмечает также сходство японского имени Сюй Фу – Оюротаюя – с именем знаменитого шпиона Такоя, о котором речь пойдет далее. Он высказывает предположение, что в предании о Сюй Фу как основателе нин-дзюцу соединились два независимых сюжета – легенда о приезде даоса в Японию и исторический факт шпионской деятельности Такоя.