Ang Simbahang ito ay itinayo sa unang kapilya na itinayo ng mga mananakop na Espanyol sa panahon ng pananakop. Ang kasalukuyang simbahan ay nagmula noong 1500 at nakalagay sa loob nito ang krus na nagpalitaw sa pagkakatatag ng lungsod.