Arctostylopids are enigmatic mammals known from the Paleocene and Early Eocene of Asia and North America. Based on molar similarities, they have most often been grouped with the extinct Notoungulata from South and Central America, but tarsal evidence links them to Asian basal gliriforms. Although Palaeostylops is the best-known arctostylopid genus, some points of its content and species level taxonomy remain uncertain. Here we report 255 upper and lower jaw fragments of Palaeostylops, five calcanea, three astragali, as well as the first known arctostylopid distal tibia. This new material was collected from the late Paleocene of the Flaming Cliffs area in Mongolia, in a single lens almost exclusively containing arctostylopid remains. Our study of the morphology and size of the new Palaeostylops dental material confirms the validity of two species, P. iturus and P. macrodon, and illustrates their morphological and biometrical variability and diagnostic differences. The distal tibia of Palaeostylops is relatively unspecialised and resembles the Asian gliriforms Pseudictops and Rhombomylus. We also review the relevance of the historically important genus Palaeostylops in view of other, more recently described but less abundant arctostylopid genera. Palaeostylops remains the reference taxon for the arctostylopid anterior dentition and postcranial morphology. For both anatomical regions, arctostylopids differ significantly from notoungulates, and present a mosaic of characters also seen in basal gliriforms. The notoungulate-like molars of Palaeostylops are highly specialized for arctostylopids and the arctostylopid molar morphotype is therefore better illustrated by the early middle Paleocene Asiostylops. This morphotype does not present any similarities to notoungulates, but shares a number of derived characters with basal gliriforms. Among gliriforms, the primitive arctostylopid morphotype is most similar to Astigale from the early Paleocene of South China, and we suggest that Arctostylopidae may therefore be more closely related to Astigalidae than to any other group.