When the early Spanish missionaries were busy laying the foundation of a church late in the 1500s at a site about six kilometers from the present town of Tuao, a big bird came circling over them and then alighted on the wooden cross erected to mark the place where the corner stone was laid. It flapped its wings noisily, cried "battuao, battuao, battuao" and then flew away.

The native laborers in the construction stopped working and refused to continue telling the priests that the site had not been well chosen. They insisted that a party should find out where the bird had flown to.

To humor the pagan natives, one of the priests allowed himself to be led by a party of natives to look for the mysterious bird. To his surprise, they found the bird serenely perched on top of a tall tree on the edge of a wide clearing ideal for a town site. He sent one of the natives to call for the other priests, who, on their arrival, found the place much to their liking. And so the first church of Tuao was constructed on the site where the present edifice now stands.

When the civil authorities founded the town in 1604, the natives insisted that it be called Tuao. Eight years later on May 13, 1612, Tuao was accepted ecclesiastically. Father Miguel de San Jacinto, O.P. gave the town Santos Angeles Custudios (Holy Guardian Angels) as its patron saints.

The early missionaries in Tuao were zealous evangelists and tactful pacifiers of warlike natives. One of them was Father Francisco Capillas who later became the first martyr in China. The first parish priest, Father Juan B. Cano, O.P. worked patiently with the people.

A late comer, Father Gabriel Serrano, O.P. built a strong brick and mortar church, a rectory (convento) and a fort (cotta) in which the Spaniards and the natives sought refuge every time the town was raided by the Kalingas from the Caraballo ranges. Unfortunately, these priceless monuments to the politicalization and evangelization of Tuao by the Spaniards were destroyed by a strong earthquake on December 29, 1949.

In protest of abuses committed by some Spanish civil petty officials and soldiers, the inhabitants of Tuao and neighboring Malaueg, rose in revolt in 1781 under Magtangaga and Tomas Sinaguingan. The uprising was put down by Capitan Juan Pablo de Orduna.

Tuao became famous nationwide during World War II as the seat of the successful renaissance government of Governor Marcelo Adduru. The Japanese Forces garrisoned the town when Adduru was captured late in 1943, but Adduru returned shortly after having been freed by his guerilla soldiers early in 1944 and with his contact with Blackburn, staged from Tuao stronger guerilla actions against the Japanese in Tuguegarao.