Depois de o embarque ser decidido, entregaram Paulo e mais alguns presos aos cuidados dum centurião da corte augusta, chamado Júlio. Este era um homem naturalmente bom e deixava a Paulo bastante liberdade. Aliás, gostava de falar com ele com frequência, porque Paulo era um prisioneiro muito diferente dos outros E, por isso, Paulo pôde despedir-se à vontade dos seus amigos e cristãos.

O barco levantou ferro do porto de Cesareia e, depois de quinze dias de viagem, chegou a Mira, sul da actual Turquia. Aí, o centurião romano encontrou um outro barco que tinha vindo de Alexandria e seguia viagem para a Itália. Os presos foram transferidos para esse barco. Durante os primeiros dias de viagem, o vento foi de feição e não houve problemas de maior. Mas, já perto da Ilha de Creta, o tempo mudou de repente. O vento soprava do lado contrário e eles não conseguiam sair do mesmo sítio. Além disso, a navegação tornava-se perigosa. Estavam, pois, diante dum dilema: prosseguir ou voltar para trás.

Paulo foi então ter com o capitão do navio: «Segundo a minha opinião, nesta altura do ano, vejo que a travessia não pode ser levada a cabo sem risco e graves prejuízos. Tanto a carga como a vida das pessoas correm perigo. Se fosse eu, procuraria um lugar seguro para passar a estação do Inverno. Eu pressinto que se aproxima uma grande tempestade!». «Não se meta em coisas que não lhe dizem respeito!» – respondeu-lhe o capitão – «Afinal, eu é que sou o capitão e, além disso, o nosso piloto é um homem muito experiente. Portanto, pouca conversa!». Como é evidente, Paulo não teve outro remédio senão acatar a decisão. Até porque, e não nos esqueçamos disso, Paulo não passava dum prisioneiro.

Voltar para o porto de Mira não era aconselhável, porque era um porto pequeno e não dava garantias para passar o Inverno. Então, a maior parte da tripulação foi de parecer que poderiam ainda chegar à Fenícia, onde havia melhores condições. Ao princípio, tudo correu bem e o vento até ajudava. Mas, com o passar dos dias, o tempo encarregou-se de demonstrar que Paulo é que tinha razão. Vindo dos lados da Ilha de Creta, desencadeou-se um vento ciclónico. As ondas cresceram e esperava-se o pior a todo o momento. O piloto perdeu o comando do barco que, devido à força do vento, começou a andar à deriva...

Felizmente, ainda tiveram sorte. Conseguiram, ainda assim, fazer passar o barco por detrás duma ilha, chamada Clauda, onde havia um abrigo que os protegia da ventania. Com bastantes dificuldades, conseguiram então lançar à água o salva-vidas e amarraram cordas grossas ao redor do caso do navio. Assim, sempre podiam aguentar melhor o embate. Só que era apenas uma medida de emergência. Mas a tempestade continuava a fustigar o barco. Então viram-se obrigados a deitar a carga ao mar. Mas, nem assim, o capitão sabia o que devia fazer e até ele, que não costuma ter medo, se começou a encher de susto. Na mente de todos ia-se desvanecendo toda a esperança de salvação.

Há muito tempo que ninguém comia, até porque não havia de comer. Finalmente, Paulo foi para o convés e gritou mais alto que o próprio vento: «Devíeis Ter-me escutado e não largar de Creta. Mas, agora, não há nada a fazer. Só que não podemos desanimar e desistir. Mesmo que os vossos deuses do mar não vos ajudem, eu posso-vos garantir o seguinte em nome do meu Deus: Deus não nos vai abandonar. Nenhum de nós irá perder a vida. Coragem, porque só o navio é que se vai perder. Esta noite, apareceu-me um anjo de Deus e garantiu-me isso mesmo. Eu tenho que chegar a Roma e encontrar-me com as autoridades romanas e, em atenção a isso, todos chegaremos sãos e salvos». Os outros tripulantes ficaram a olhar para Paulo sem fazer qualquer comentário. Limitaram-se a encolher os ombros.

A tempestade durou catorze dias. De repente, numa noite, o navio estremeceu todo. Rangeu e deu uma espécie de pino para a frente. O capitão quase que caiu para dentro da cozinha. O navio tinha encalhado num banco de areia. Era muito escuro. Mas, se era assim, então tinham que estar muito perto de terra firme. «Depressa, depressa!» – gritou o capitão – «Lancem já toda as âncoras. Senão, ainda vamos embater contra qualquer rocha!». A tripulação corria dum lado para o outro. Empurravam-se, impediam-se uns aos outros, esbarravam e tropeçavam sempre em qualquer coisa. Porque não se via mesmo nada. Por fim, o capitão lá conseguiu descobrir e acender a última lanterna...

Quando começou a clarear um pouco, Paulo notou que o capitão e vários marinheiros correram para o lugar onde havia ainda dois salva-vidas. «O que é que os senhores têm a ideia de fazer?» – gritou Paulo. «Bem!» – respondeu o capitão – «Queremos controlar e ver se as âncoras ficaram mesmo em terra firme e se o barco ficou segurou não!». Mas a verdade é que eles estavam já a lançar os salva-vidas para fugir, deixando os prisioneiros e os soldados à sua sorte... Paulo então não teve outra saída senão ir chamar os soldados que vigiavam os presos: «Depressa, depressa! A tripulação está a escapar. Querem abandonar o navio e deixar-nos a todos cá. Se estes homens não ficam no barco, todos nós estamos perdidos!». E logo dois ou três soldados foram a correr e, puxando da espada, cortaram as amarras que seguravam os salva-vidas...

«Escutai-me, por favor!» – começou a dizer Paulo ao capitão e à tripulação – «Vós estais loucos de medo e isso é compreensível depois destes catorze dias terríveis. Mas, mesmo assim, é preciso manter a capacidade de pensar. Reparai: se vós tivésseis partido nos salva-vidas, teríeis morrido ainda mais depressa do que nós. Juntos é que não morreremos. Agora, o que é preciso fazer é comer alguma coisa, mesmo que não tenhamos vontade. A nossa própria salvação está em jogo. Se fizerdes como eu digo, ninguém se perderá». E o próprio Paulo deu o exemplo. Pegou no pão, abençoou-o, deu graças a Deus e comeu. Os outros, vendo Paulo, cobraram um pouco de ânimo e comeram também. Havia no barco, ao todo, duzentas e setenta e seis pessoas. Uma vez saciados, aliviaram o barco, lançando o resto ao mar. Finalmente, Paulo concluiu dizendo: «Agora, vamos esperar que mais um pouco. Depois, logo se verá o que podemos fazer!».

Passadas algumas horas, o marinheiro mais jovem gritou para toda a tripulação: «Terra à vista! Terra à vista!». E, de facto, no horizonte acabava de nascer um sol grande e pálido, que começava a iluminar todo o horizonte. Lá ao longe, via-se na bruma daquela manhã fria o contorno cada vez mais nítido de algumas montanhas e de algumas planícies. Os que eram capazes de nadar foram sozinhos para terra. Os outros foram levados quer em pranchas quer sobre os destroços do barco. Só depois de sãos e salvos é que ficaram a saber que a Ilha se chamava Malta. Os nativos trataram-nos com invulgar humanidade.