Gapan was founded by Spanish friars and officials sometime in the middle of the sixteenth century as one of the first towns of Pampanga.

Records of the first Catholic mission to the Far East indicate that in 1595, Fathers Contreras, Tendilla, Caballo and Salazar cleared a forest which later became a pueblo, with a church, presidencia and houses made of bricks and lime which to this day constitute the age-old landmarks of the city.

At over four centuries old, the Three Kings Parish is the oldest in Nueva Ecija and one of the oldest in the Philippines.

It covered a big pueblo, reaching as far north as Cabanatuan until the latter became a separate town in 1777; the Sierra Madre mountain range in the east; San Miguel, Bulacan in the south; and Candaba, Pampanga in the west.

In time, Gapan was divided into separate pueblos until all that remained were the present towns of Peñaranda, General Tinio and San Leonardo. In fact, legend has it that the image of Gapan's other patron saint, the Divina Pastora, was found in Barrio Callos in Peñaranda.

The Three Kings Parish which once had jurisdiction over the huge Gapan area was later subdivided to better minister to the faithful. From it were carved the San Roque Parish covering the southern barangays of the city; the San Nicholas Parish covering the western areas; and  in 2007, the Santa Elena Parish covering the eastern areas.

The Three Kings Parish now consists of the central barangays of San Vicente and San Lorenzo, Mangino and Pambuan.