La devozione a Nossa Senhora da Penha de França (cioè: di Francia) ha origine in Europa fin dal sec. XV, quando un certo Simão Vela, pellegrino francese, ne scoprì l’immagine sul monte Penha de França nei pressi di Salamanca, il 19 maggio 1434.
A Rio de Janeiro, tutto cominciò verso la metà del sec. XVII, il 1635, quando il capitano Baltazar de Abreu Cardoso ebbe la grazia di un provvidenziale intervento della Vergine presso una grande roccia (penhasco) in un’area di sua proprietà, dove sarebbe poi sorto il Santuario. Imbattutosi in un enorme serpente velenoso, Baltazar, che era molto devoto di Nossa Senhora, ne invocò l’aiuto ottenendo che un grosso lucertolone dell’ordine dei sauri ingaggiasse la lotta contro il serpente, uccidendolo.
In segno di ringraziamento alla Madonna, Baltazar vi costruì una piccola cappella, collocandovi l’immagine di Nossa Senhora da Penha da lui venerata.