Recent literature is controversial as regards the segregation of Hallea and Mitragyna, and pretends that the two genera show pollen morphological differences. In the present study the pollen morphology of all ten species of the complex is described on the basis of light and scanning electron microscopy (including examination of broken grains, which were obtained with a technique never applied in palynology, viz. shaking with glass beads). The two genera have 3-zonocolporate grains with compound apertures (endoapertures are always H-shaped, sometimes incompletely so). While Hallea showed to be stenopalynous (sexine always tectate-perforate), Mitragyna is more variable (sexine microreticulate or tectate-perforate), and several of its species have pollen similar to that of Hallea. Numerical analysis was used to evaluate the palynological observations in the light of the macromorphological variation in the complex. It is concluded that both Hallea and Mitragyna deserve generic recognition, but are not fully distinct pollen morphologically.