Valenzuela's history would be incomplete without the history of its home province, Bulacan. Valenzuela, Obando, and Novaliches (now in Quezon City) were all part of Bulacan for hundreds of years. As a result, before 1623, Bulacan's history was also Valenzuela's history.
The area encompassed by the present-day Valenzuela City, Novaliches, and Obando municipality and portions of land in southern Caloocan City were formerly known during Spanish period as Polo. The region, is significantly bounded by the Tullahan River on the south and streams of branching Río Grande de Pampanga on some areas.
According to Philippine historians Emma Helen Blair and James Alexander Robertson, there existed an infamous Battle of Bangkusay in Bangkusay Channel, Tondo headed by Maynila king Rajah Sulayman, which employed seafarers and warriors from all over parts of the north of Maynila Kingdom and Bulacan. The battle was declared against Spanish conquering forces of Miguel López de Legazpi on June 3, 1571. Spanish troops were headed by Legazpi's nephew, Martín de Goiti. On June 3, 1571, Sulayman led his troops and attacked the Spaniards in a decisive battle at the town of Bangkusay, but they were defeated, and Sulayman himself was killed. With the destruction of Sulayman's army and the friendship with Rajah Lakandula, the Spaniards were enabled to establish throughout the city and its neighboring towns.
Legazpi formally established settlement on Maynila on June 24, 1571. According to Father Martinez de Zuñiga, a Spanish missionary of Augustinian order, Maynila was a vast region enclosed by the towns of Polo, Tambobong (now Malabon City), and mountains of San Mateo in Morong. The region of Valenzuela, was formally merged under the rule of Bulacan town of Catanghalan.
On 1587, the Tagalog cabeza de barangay of Catanghalan Tassi Bassi joined the Tondo chieftain Magat Salamat's planned insurrection against Spanish colonization of Maynila. The rebellion was composed of kin-related noblemen or maharlikas of Maynila including Juan Banal, another Tondo chief and Salamat’s brother-in-law; Gerónimo Basi and Gabriel Tuambacar, brothers of Agustín de Legazpi; Pedro Balinguit, the chief of Pandacan; Felipe Salonga, the chief of Polo; Dionisio Capolo (Kapulong), the chief of Candaba and brother of Felipe Salonga; Juan Basi, the chief of Taguig; Felipe Salalila, the chief of Misil; Agustin Manuguit, son of Felipe Salalila; Luis Amanicaloa, another chief of Tondo; Felipe Amarlangagui, the chief of Caranglan; Omaghicon, the chief of Navotas and Pitongatan (Pitong Gatang), another chief of Tondo. In Philippine history, this was notably known as Tondo Conspiracy of the Maharlikas, a plot of series of "revolution" against Spain that included several native noblemen. The planned revolution was never happened because whistleblowers revealed the nature of it to Spanish authorities.
When Manila became an archdiocese on August 14, 1595 based upon Pope Gregory XIII's Papal order, regular friars that had already established permanent church in Catanghalan decided that the attached sitio of Polo be divided to cater spiritual needs of an increasing population all over. Thus, on 1623, upon order of Governor-General Alonso Fajardo de Entenza, sitio Polo became independent from Catanghalan although the two was still under the alcaldía (Spanish title for local government during that time) of Bulacan.
Regular friars dwelling in the town of Catanghalan requested an appeal from Governor-General Entenza to have another separate town from the former prior to the elevation of Manila as an archdiocese in 1595. Sitio Polo was effectively detached from Catanghalan in 1623, but remained under the jurisdiction of the alcalda de Bulacán, thanks to the efforts of Fray Juan Taranco and Don Juan Monsód. As a result, Monsód was the first cabeza de barangay in the new town of Polo, and Taranco governed the current San Diego de Alcalá parish from a small tavern.
It was in the year 1627 when the construction of the Parochial church dedicated to San Diego de Alcala started. Finally, in 1629, the church was fully constructed. Its fabrication was supervised by Fr. José Valencia aided by Capitan Juan Tibay. The church was fully repaired and remodeled under the direction of Fr. Vicente in 1852. A great change took place in the appearance of the church, that according to the missionaries it was one of the best ever built in the archipelago, and became the envy among other towns. Again, the church after its repair was dedicated to another patron, the "Nuestra Senora de la Inmaculada Concepcion". Still, another dedication was made and that was to San Roque. The convent was well built and comfortable. The pride of its artistry lies on the fact that the people of the town had done so much to its perfection. Besides the convent, a descent "casa tribunal" with a rectangular prison cell was built, and a school house also fabricated of stones was erected.
During 1635, the Sangleys at Parian in Manila and in the neighboring towns staged an insurrection against the Spanish government. It was during one of these rebellions that the church bells brought by the Spanish Missionaries to the town which was made of bronze, and whose intonations were second only to that of the bell of St. Peter's Basilica in Rome, was stolen by the Chinese. Since it was so huge, the looters had to break it into small pieces in order to remove it from the belfry.