Cacti constitute one of the most iconic and highly diversified groups of plants in the Americas, as Mexico, the Andean region, and eastern Brazil are the main centers of diversity. For many years, its divergence time has been the central question and an enigmatic topic since research has always been hindered by the scarcity of fossil records. The present study documents the palynological diversity of tricolpate and pantocolpate pollen grains with Cactaceae affinity during the Middle Miocene in the Tehuacan-Cuicatlan Valley, an important center of cactus diversity in south-central Mexico. Aridity during this period coincides with the Mid-Miocene Climatic Optimum and is supported by evaporitic rocks from the upper part of the Tehuacan Formation (TF). Tricolpate pollen grains similar to Cephalocereus-Mammillaria cactus genus, were less abundant in the TF, and cluster analysis distinguished three groups. Furthermore, principal component analysis (PCA) showed that the polar area index, the distance between the apices of the colpi, and the equatorial diameter were the characteristics that explained the maximum variance among the tricolpate specimens. In addition, three groups were identified among the pantocolpate specimens with affinities to the genus Pereskia-Opuntia. PCA of the pantocolpate pollen grains revealed that pollen diameter, columella diameter and density, columella length, exine thickness, and spinule density explained the maximum variance among these grains. Miocene pollen grains from Cactaceae were shorter than those of modern species, suggesting that adaptations to the arid climate may have triggered polyploidy and an increase in pollen grain size.