Kazachostylops occidentalis Nesov, 1987, based on partial maxilla and dentary from the upper Paleocene Zhylga locality in South Kazakhstan, is redescribed. A new phylogenetic hypothesis of Arctostylopida is proposed based on phylogenetic analysis of 26 characters and 17 taxa. Kazachostylops is recovered as a sister taxon to the Arctostylopinae, the advanced clade of Asian and North American arctostylopids characterized by pseudohypocone on upper molars and reduced trigonid of lower molars, with the ectolophid being attached labial on the trigonid. Kazachostylops differs from more basal arctostylopids (Asiostylops, Allostylops, Bothriostylops, and Wanostylops) by higher-crowned molars, M1-3 metaconule absent, m1-3 entoconid connected with ectolophid by entolophid, and m2 wider than m1 and m3. Principal component analyses of the upper and lower dentition of arctostylopids show great distinctness of Kazachostylops from other members of the group. The arctostylopid taxa are reviewed, and the new genus Enantiostylops is erected for ‘Sinostylops’ progressus Tang and Yan, 1976 from the lower Eocene of China, because of uniquely concave parastylar area on upper molars.