Pouco depois se mudou para Portugal, onde obteve licença do Custódio Frei Damião da Torre de, em 1558, embarcar para a Capitania do Espírito Santo, no Brasil. Na viagem, a embarcação foi tomada de forte tempestade, correndo perigo de naufragar. No desespero, lembraram-se os navegantes do religioso, companheiro de viagem, cujas santas virtudes já eram admiradas. Recomendaram-se às suas orações e um tomou-lhe o manto e, com ele, tocou as ondas, que imediatamente se aplacaram, permitindo próspera travessia. Desde então Frei Palácios só era chamado de o santo frade. Este fato é histórico, contado por todos os autores. Depois de feliz viagem, o navio chegou à Capitania do Espírito Santo, em Vila Velha. Os companheiros de viagem se espalharam pela localidade e Frei Palácios cuidou do seu destino. Dias depois, porém, lembraram-se do religioso, que havia granjeado todo o seu afeto, e sabendo também os moradores da presença do santo homem, todos tiveram desejo de saber onde ele estava. Procuraram-no e só depois de três dias encontraram-no numa cabana na montanha.Segundo a tradição local, o lugar do encontro foi um vão formado pela natureza em baixo de uma grande pedra, situada no sopé da montanha, junto à praia, ao lado esquerdo de quem entra pelo atual portão da “Ladeira da Penitência”. Ainda hoje é conhecida por “Gruta de Frei Palácios” e, desde 1864, é assinalada por uma lápide comemorativa, que mandou colocar o Guardião Frei Teotônio de Santa Humiliana. Não querendo, pois Frei Palácios descer da montanha pediu aos moradores lhe construíssem uma capela na parte plana da rocha. Fizeram-no e ele dedicou-a a São Francisco de Assis, colocando sobre o altar a imagem de Nossa Senhora da Penha e a imagem do Patriarca São Francisco. A morte do Servo de Deus se deu em 1570 e em 18 de fevereiro de 1609 os despojos foram exumados e transladados para a Igreja do Convento de São Francisco da cidade de Vitória.