Small phosphatised fossils from late Cambrian limestones of Västergötland, Sweden, share major external features with larval extant Pentastomida, such as a prominent head with two pairs of stumpy limbs adapted for attachment, and a slender trunk of four portions. Even such details, as paired forehead structures, pores on the inner edges of the head limbs and paired papillae at the rear of the trunk correspond with structures of extant pentastomid larvae. Neither the fossils nor the Recent pentastomids add any additional body segments during growth (segment constancy). Since characters of this kind and in this combination do not occur elsewhere, the fossils are recognised as true Pentastomida. Major differences, such as distinctly divided head limbs, partial occurrence of vestigial trunk limbs, and a different mode of trunk development during growth can be explained as representing merely the plesiomorphic state of characters of Pentastomida, indicating that the fossils are representatives of its stem-group prior to branching into the two Recent lineages. The fossils clearly document the marine origin of the Pentastomida, and that their specific morphology and parasitic life style were already established in the late Cambrian at a high degree of diversification, long before the terrestrialisation of their present final hosts, the tetrapods. General arthropod affinities are recognisable not least in the nature of the limbs, but the morphology of stem- and crown-group pentastomids gives no clues for closer relationship with any of the major (eu)arthropod taxa.