The present Archdiocese of Cagayan de Oro had its beginnings as a territory of the Archdioceses of Cebu and Jaro from 1607 to 1910. Its administration is later transferred to the Diocese of Zamboanga from 1911 to 1933 before its canonical erection in 1933. During its early history, it was believed that the first church structure built in present-day Cagayan de Oro was erected in 1624 by the Augustinian Recollects under the leadership of Father Agustin de San Pedro. The old settlement used to be located in an area called Himologan or Huluga. It was moved to its present location due to Father San Pedro's urging, reasoning out that the current location would be easier to defend from marauding pirates and other enemies. The church structure during that time was made of light materials with fortification built of the same materials. The church was frequently attacked and razed to the ground by soldiers from the Non-Christian areas of Mindanao. One such instance happened in 1649, when a Manobo tribe under the leadership of a certain Dabao revolted against the presence of the Spanish government and church in the area. After the incident, the church was rebuilt with wood and other light materials until it was again burned in 1778. The following year, Father Pedro de Santa Barbara led the construction of a new and bigger church. The said church, like its predecessors, was also razed by fire in 1831. After the most recent fire, the church officials did not rebuild the church until 1841 when Father Simon Loscos instigated the construction of a stone church. The town mayor during that time, Don Jose Corrales, together with members of the local clergy, helped in the construction of the stone church. The church construction lasted from 1843 to 1851. In 1886, the parish priest of Cagayan de Oro, Father Ramon Zueco, bought a pipe organ from Manila. In 1942, during the Second World War, the church of Cagayan de Oro was bombed. Soon after the war, the construction of the present cathedral structure was started. It was not specified when the current Neo-Gothic cathedral was completed.
