Palpigradi are a poorly understood group of delicate arachnids, often found in caves or other subterranean habitats. Concomitantly, they have been neglected from a phylogenetic point of view. Here we present the first molecular phylogeny of palpigrades based on specimens collected in different subterranean habitats, both endogean (soil) and hypogean (caves), from Australia, Africa, Europe, South America and North America. Analyses of two nuclear ribosomal genes and COI under an array of methods and homology schemes found monophyly of Palpigradi, Eukoeneniidae and a division of Eukoeneniidae into four main clades, three of which include samples from multiple continents. This supports either ancient vicariance or long-range dispersal, two alternatives we cannot distinguish with the data at hand. In addition, we show that our results are robust to homology scheme and analytical method, encouraging further use of the markers employed in this study to continue drawing a broader picture of palpigrade relationships.