The settlement of Himologan was located on a cliff overlooking this river. In 1626, another Augustinian Recollect friar was assigned to Cagayan, the young Portuguese Fray Agustin de San Pedro. He was only 26 years old but was trained in mathematics, architecture, gunnery, and military skills at the University of Salamanca before joining the Augustinian Recollect order. The Recollect chronicles relate that Fray Agustin convinced the leader of Himologan, Datu Salangsang, to move the site of his settlement down river, to the area of today's Gaston Part and San Agustin Cathedral. Such was the founding of Cagayan in the year 1626. Here, Fray Agustin built a church of native materials where Datu Salangsang and his wife were baptized as Christians, the first converts of Cagayan. The rest of the chieftain's people followed. This was the Christianization of Cagayan.

At the time, news reached Sultan Kudarat of the coming of Spanish missionaries in the Cagayan area. Wanting to regain back the tributes that he earned from Cagayan, Kudarat sent a fleet of warriors to drive away the Spanish missionaries. It was because of the frequent tensions with Kudarat that drove Fray Agustin to build a fortress and watchtower in Cagayan to protect the native population. Fray Agustin's defense of Cagayan made him known as "El Padre Capitan". This wooden fortress, known as the Fuerza Real de San Jose, was located around the area of today's Gaston Park which contained the church and garrison as the center of town. The fortress was rebuilt much later in stone in 1730, but was demolished in 1875 by then the Spanish politico-military governor of Misamis, Lt. Col. Jose de Carvallo, who used the stones to pave the streets of the town.

The Recoletos established Cagayan as their mission center in 1674, San Agustin as the patron of Cagayan was adapted only on August 28, 1780. The first church built earlier by the Recoletos was reconstructed in 1845 by Fray Simon Loscos de Santa Catalina. It was made of marine stones imported from China and had protruding buttresses and a single belfry. Inside, there was a magnificent altar and sanctuary with carved wooden niches and paintings. This church was destroyed during the bombing of Cagayan in 1945, exactly a hundred years after its reconstruction.

In 1818, the Spanish colonial government in Manila divided Mindanao into politico-military districts. Cagayan became a part of the Segundo Distrito de Misamis, the largest district in Mindanao which encompassed today's Misamis Oriental, Misamis Occidental, Camiguin, Bukidnon, Lanao, Zamboanga del Norte, and the northern part of Cotabato. However, the capital of the district was the town of Misamis along the Bay of Panguil, today known as Ozamis City, where there was a much bigger Sapnish fort and garrison. The name of the district, in fact, was derived from that town. It was only on February 27, 1872 that Spanish Governor General Carlos Maria de la Torre issued a decree in Manila adapting Cagayan as the permanent capital of the District of Misamis. The Spanish politico-military governor of Misamis, who always carried the rantk of lieutenant colonel, resided at the Casa Real de Cagayan, built in 1831, the site of today's City Hall of Cagayan de Oro. During this era, the name of the town was "Cagayan de Misamis".