Брендан, услышавший этот рассказ, избрал четырнадцать монахов, чтобы с ними отправиться на поиски райской земли. Сорок дней постились избранные, а затем построили корабль из легчайшего дерева и наполнили его припасами на сорок дней. Еще три монаха бросились к ногам Брендана, чтобы он допустил их до благочестивого плавания, и тот согласился, но предрек, что лишь один из них движим благочестивыми помыслами, двоим же другим не миновать Страшного суда.
Корабль тронулся в полуденную сторону. Когда гребцы обессилили, Брендан доверился воле ветра и корабль сам пошел под развернутым парусом. Наконец, паломники приплыли к скале с отвесными склонами и с трудом нашли гавань, куда помещался лишь один корабль. Тут перед путниками появился пес и стал ластиться к ним, как к хозяевам. Он привел их в некий город, где открыты были ворота дворца, полного всякой богатой утвари. Только лишь Брендан велел приготовить трапезу, как они увидели накрытый стол, полный яств. Так три дня отдыхали путники, Брендан же предупредил спутников, что их может смутить Сатана и поэтому нельзя ничего брать из богатств во дворце. Святому привиделось во сне, что один из монахов взял уздечку, которой помахивал перед ним дьявол в образе эфиопа. И правда, один из монахов сознался, что присвоил драгоценную вещь, и тут же выбросил ее из-за пазухи. Брендан изгнал дьявола, притаившегося там же в виде чернокожего. Тут раскаявшийся монах испустил дух, но душа его была спасена.
Пора было трогаться в путь, и некий отрок явился на корабль с корзиной яств, пообещав, что этого хватит путешественникам до самой Пасхи. И правда, еды хватило на два дня – ровно столько они плыли до следующего острова. Когда наступил Великий четверг, странники достигли острова, где было изобилие рыбы и бесчисленное множество овец, которые размерами превосходили быков. Из их числа был взят агнец для святой трапезы. Там провели путники время до субботы, а в воскресенье должны были плыть дальше, к острову, что называется Птичьим раем. Чудесный слуга предрек им достаток в пище вплоть до Пятидесятницы, приготовив все на дорогу.
Но следующий остров, который был у них на пути, был пустынен, и на нем не росло ни одного дерева. Святой понял, что это за остров, но не стал сразу пугать монахов. Те успели высадиться на острове, и когда они разожгли костер, остров пришел в движение. В ужасе монахи бросились к кораблю, и Брендан помог им подняться на борт. «Этот остров – самая большая в мире рыба, – поведал им Брендан. – Она настолько огромна, что не может носом дотянуться до своего хвоста».Вспоминается скандинавский Ёрмунганд – Мировой змей, опоясавший Вселенную. Однако у христианских авторов были собственные представления о морском чудовище, обитающем в мировом океане: то был библейский Левиафан. Правда, в странствии Брендана Левиафан – уже воплощение преисподней, а «рыба-кит» Мирового океана носит иное имя.