In 1622, Palawan (Paragua) and the neighboring northern islands collectively known as Calamianes were entrusted to the spiritual care of the Augustinian Recollects by the Bishop of Cebu, Pedro de Arce OAR. Friars Francisco de San Nicolas, Diego de Santa Ana, Juan de Santo Tomas and lay brother Francisco de la Madre de Dios were assigned to this mission area. By 1623, the friars had crossed to the Palawan mainland but failed to succeed in conversion because of the strong influence of Muslim communities. Quite a contrast to the easy acceptance of Catholicism by the people of Cuyo and neighboring Agutaya. These fledgling Christian outstations were subject to attack by slave raider: 1632 Cuyo; 1636 Cuyo and Calamines; and in 1646 the raiders planned a concerted and massive attack on this frontier. In 1638, while serving as parish priest of Cuyo, Juan de Severo, OAR conceived of the idea to fortify the churches of Cuyo, Agutaya and Culion. While the friars built churches and residences and were advancing in their work, continued slave-raiding and lack of resources forced them to abandon Palawan briefly, except for Cuyo and Agutaya. This retrenchment set back the growth of the missions. In 1659, they returned determined to stay and so begun the construction of more durable defensive fortifications at Cuyo, Agutaya, and Culion, and also at Linapacan, Taytay and Dumaran, Malampaya, Calatan and Paragua (Puerto Princesa). In 1692, the mission at Agutaya was raised to the status of parish under the advocacy of San Juan Bautista. This is the same name given to the fort at Agutaya.
The fort built in 1683 was remodelled in the 18th century. It is not certain if the 17th-century fortification was a palisade or a stone fort. The plan for Agutaya appears in the Valdes Tamon report of 1738. Whether the fortification was built immediately is uncertain. A date given for the completion of the fort is 1784 and is attributed to the encomendero Antonio de Rojas who delineated the plan of the fort. Apparently, the earlier fort of Fray Juan was greatly modified.
Landor (1904: 65) describes Agutaya “a fort with four battlements was the principal structure, and inside its quadrangle was to be found a simple and modest church, the windows of which were cut into the east wall of the fort. This house of God possessed a choir-balcony and the usual cheap images of the altar. On the northeast battlements, which was crumbling away were the remains of a high tower.”
The degradation of the Agutaya fort continues to this day.