La población tiene una antigüedad que se remonta al año 1200 a. C. Aproximadamente, la historia nos dice que por los años 1400 de nuestra era, se le conocía con el nombre de Huijazoo.

La población tiene una antigüedad que se remonta al año 1200 a. C. aproximadamente; la historia nos dice que por los años 1400 de nuestra era, se le conocía con el nombre de Huijazoo y años más adelante, cuando fue conquistada por las tropas mexicas, el poblado paso a llamarse Guaxolotitlan y por los años 1700 su nombre fue cambiado por el nombre de Huitzo que es con el que se le conoce actualmente, cuando los españoles llegaron en 1522 al hoy estado de Oaxaca, bajaron a los pobladores que vivían en las cimas del lomerío que se localiza hacia el oriente de la actual población y fundaron el nuevo poblado en un lugar cercano al río Atoyac.

Los primeros frailes que llegaron a evangelizar a los Indígenas y poblaron al hoy Estado de Oaxaca, seleccionaron al Apóstol San Pablo para que fungiera como el patrón del lugar y escogieron el día 25 enero, para la fiesta titular, por ser el día en que la Iglesia Cristiana registra la conversión del Ciudadano Romano a la Iglesia Católica, en el exconvento del siglo XVI.

El pueblo se encuentra dividido en 3 secciones y una agencia municipal, Santa María Tenexpan.

La festividad principal de la población es en honor a San Pablo Apóstol (a quien debe el título) esto es en la primera sección, donde se encuentra un exconvento dominico, ahora la iglesia de la población.