Systematic sampling of the Mesovoid Shallow Substratum (MSS) at several sites in three regions of the Iberian Peninsula has revealed two new and one very poorly known species of the genus Archipolydesmus Attems, 1898. These are the first records of Archipolydesmus in the MSS, although the genus had previously been recorded from several caves in southern Spain. Archipolydesmus foliatus sp. nov. shows inter-population variability between different mountain massifs of the province of Alicante, as well as intra-population variability at some sites; A. altibaeticus sp. nov. exclusively inhabits the MSS of the highest screes of Sierra Nevada (3000 masl) in the province of Granada, and it closely resembles Archipolydesmus maroccanus Attems, 1898; from North Africa; Archipolydesmus bedeli ( Brölemann, 1902) had only been re-collected once since its description, and the male, hitherto unknown, is described here. Detailed SEM documentation of the main characters of each species is provided, and a discussion on the implications of these findings in the MSS is provided. Also, a distribution map, an updated key to species of the genus in English, and a brief review of millipedes found in the MSS are provided.