Simão Vela, assim se chamava o monge, durante cinco anos andou procurando a mencionada serra, até que um dia teve indicação de sua localização e para lá se dirigiu. Após três dias de intensa caminhada e escalando penhas íngremes, o monge parou para descansar, quando viu sentada perto dele uma formosa senhora com o filho ao colo que lhe indicou o lugar onde encontraria o que procurava. Auxiliado por alguns pastores da região, conseguiu achar a imagem que avistaram em sonho.

Construiu Simão Vela uma tosca ermida nesse local, que logo se tornou célebre pelo grande número de milagres alcançados por intermédio da Senhora da Penha, e mais tarde ali foi construído um dos mais ricos e grandiosos santuários da cristandade.

Aceitando a sugestão, o escultor luso executou a obra e colocou-a na ermida da vitória, mas algum tempo depois resolveu edificar-lhe uma igreja em local próximo a Lisboa e que mais tarde se tornou conhecido como Penha de França.

Naquela época, uma peste assolou o país e como a Espanha se livraria do flagelo graças à intervenção de Nossa Senhora da Penha, o Senado da Câmara de Lisboa prometeu à Mãe de Deus construir-lhe um grandioso templo, se Ela livrasse a cidade da moléstia. Extinguiu-se a epidemia quase subitamente, a Câmara mandou edificar magnífico santuário naquele local.

Este tempo passou a atrair milhares de peregrinos e em certa ocasião um devoto, tendo subido ao alto da penedia, vencido pelo cansaço adormeceu. Uma grande cobra aproximou-se para picá-lo quando um enorme lagarto saltou sobre ele despertando-o a tempo de matar a serpente com seu bastão. Essa é a razão pela qual a imagem de Nossa Senhora da Penha tem aos pés um peregrino, a cobra e o lagarto.

Como quase todos os títulos da Virgem Maria registrados no Brasil no período colonial, o culto de Nossa Senhora da Penha foi trazido por marujos portugueses e aqui tomou grande impulso, devido à devoção dos lusitanos emigrados que transpuseram para nossa pátria os seus costumes e devoções.

Um dos mais famosos templos brasileiros dedicados a esta invocação é o de São Paulo. Segundo os antigos cronistas, um viajante francês seguia de Piratininga para o Norte, levando em sua bagagem uma imagem de Nossa Senhora da Penha de França. Ao passar pelo morro chamado então Aricanduva, parou para descansar. Ao continuar o trajeto no dia seguinte, notou a falta da santa. Voltou para procurá-la e foi encontrá-la no lado do morro de Aricanduva. Guardou a imagem no baú e prosseguiu viagem, mas, ao chegar no pouso seguinte, notou a falta da efígie, que foi encontrada novamente no local onde pousara. Este fato repetiu-se várias vezes e ele, vendo nisso a vontade do céu, ali plantou uma pequena ermida.

O padre Jacinto Nunes, filho de um dos primeiros habitantes de São Paulo de Piratininga, transferiu a imagem e a capela para o alto do morro onde se encontra a secular matriz da Penha. Não sabemos exatamente a data da fundação deste templo, mas é certo que em 1667 ela já existia e era cercado de alpendres como as mais antigas igrejas do Brasil. Em 1687 o bispo D. José de Barros alarcão quis transferir a imagem de Nossa Senhora da Penha para um recolhimento, mas as mulheres do bairro se revoltaram e a Padroeira ali permaneceu. Ela é atualmente a Protetora da cidade de São Paulo e sua igreja está coberta de promessas e ex-votos.

A ermida da Penha, no Rio de Janeiro, foi fundada no início do século XVII pelo capitão-mor Baltasar Cardoso, senhor de um engenho de açúcar naquela localidade, tendo sido substituída pelo atual templo construído no século XIX, que se avista de todo o litoral da Guanabara.

A festa de Nossa Senhora da Penha realiza-se no Rio de Janeiro em outubro e é a solenidade religiosa mais popular da bela metrópole guanabarina. Centenas de peregrinos vindos de várias partes da Cidade Maravilhosa e de outros Estados sobem devotamente os 365 degraus cavados na rocha, a fim de agradecerem à Virgem Maria alguma graça alcançada, ou para rogarem pela saúde de seus entes queridos. Esta festividade, que se celebra desde 1713, é sempre acompanhada de folguedos populares e animada pelas músicas e danças em homenagem à Santa Padroeira. Atualmente, entretanto, ela tomou nova feição e ganhou maior colorido e afluência, devido às obras de reforma e melhoramento do parque da Penha, empreendidas pelo governo do antigo Estado da Guanabara.

A história e a lenda de Nossa Senhora da Penha de Vitória, no Espírito Santo são ainda mais antigas que as da ermida paulista.

Num belo dia de maio do ano de 1535, em terras goitacás no meio da mata, onde se podia ouvir o grito dos papagaios, e o farfalhar das folhas das árvores gigantescas, um ruído estranho ecoou pelos ares. Era um tiro de canhão, talvez o primeiro a ser ouvido em plagas capixabas. A caravela "Glória" acabava de fundear na enseada da futura Vila Velha, trazendo o donatário Vasco Fernandes Coutinho, fidalgo português que havia deixado sua abastada Quinta no Alenquer para tomar posse da capitania, à qual deu o nome de Espírito Santo.

A esperança que o dominava ao desembarcar nas praias do Novo Mundo foi aos poucos se apagando devido às lutas entre colonos e naturais da terra e Vasco Coutinho mandou vir do Reino alguns padres a fim de pacificá-los. Entre os missionários que ali chegaram durante o governo do inditoso donatário, estava o Frei Pedro Palácios, franciscano espanhol, que trazia em sua bagagem um belíssimo painel de Nossa Senhora, o mesmo que ainda existe no convento da Penha de Vitória. Na azáfama do desembarque, não notaram os companheiros o desaparecimento do santo frade e somente após dois dias acharam-no numa gruta ao pé da montanha, onde havia exposto o painel da Virgem, convidando os fiéis à prece e à meditação.

Certo dia os devotos não encontraram Frei Pedro e nem o painel. Pelo latido do cãozinho que sempre o acompanhava, descobriram-no na escarpa do morro que domina a bela baía de Vitória. Contou então que o painel havia desaparecido e ele estava a procurá-lo. Após ingentes esforços, um grupo de pessoas conseguiu atingir o cume do monte e ali, entre duas palmeiras, encontraram a pintura. Religiosamente foi a tela reconduzida à gruta, mas diante do ocorrido, Frei Pedro iniciou a construção da Igreja dedicada a São Francisco, na chapada, junto ao cume da montanha e para lá levou o painel de Maria.

A imagem de São Francisco lá ficou, mas o quadro da Virgem novamente desapareceu sendo encontrado ainda uma vez no píncaro, entre as duas palmeiras. Resolveu então o frade construir uma ermida no cume de penhasco, e ele mesmo, velho e alquebrado, carregou os primeiros materiais até o lugar da capela. Realizado o seu grande sonho, a igreja foi solenemente inaugurada a 1^º de maio de 1570, e, enquanto se elevavam os foguetes e as manifestações de alegria dos que ali se encontravam, subiu ao céu a alma de Frei Pedro Palácios ao som dos sinos da ermida da Penha.

Após a morte de Frei Palácios, a ermida ficou a cargo de alguns devotos e amigos, que a conservaram. Esta situação perdurou até 1591, quando as autoridades de Vila Velha e de Vitória decidiram entregar a Capela da Penha aos Frades Franciscanos. Desde então, os filhos de São Francisco aumentaram a capela, e a transformaram no célebre Santuário. Em fins de 1651 teria sido lançada a pedra fundamental do Convento de Nossa Senhora da Penha. O Conventinho teve sua construção rematada em 1660 necessitando, a partir de então, de constantes melhorias e reparos.

A Festa da Penha, com romarias e afluência de devotos de todo o Brasil, acontece na primeira segunda-feira após a Páscoa. Um grande incentivador da festa foi Frei João Nepomuceno Valadares, natural de Vitória, que destacou-se como restaurador do Santuário do Convento, realizando obras de grande vulto nos anos de 1853 a 1862. Faleceu em 1865 e foi enterrado numa parede interna do Convento de São Francisco de Vitória, bem em frente à porta da sacristia.