The tropical to subtropical squat lobster Uroptychus nasoVan Dam, 1933 (Chirostylidae) is a widely distributed species originally described from Indonesia, subsequently reported from the Philippines, Taiwan, Japan and it has recently been discovered on the continental slope of north-western Australia. Populations of U. naso occur along the Indo-Pacific Ocean continental margin crossing the recently proposed marine analog of Wallace’s line, responsible for past population fragmentation and ancient speciation. Sequence data from mitochondrial (COI, 16S) and nuclear (H3) DNA regions were used to assess genealogical relationships among geographically disjoint populations of the species throughout its known distribution range. Several mitochondrial lineages, corresponding to geographically isolated populations and three cryptic species were encountered, namely, U. naso sensu stricto and two new species, Uroptychus cyrano and Uroptychus pinocchio spp. nov. U. pinocchio is encountered only in Japan, Taiwan and the Philippines; U. cyrano is confined to north-western Australia; and U. naso consists of three genetically distinct populations distributed on both sides of the marine Wallace’s line. Fossil-calibrated divergence time approximations indicated a most recent common ancestor (MRCA) for U. naso and U. cyrano from early Eocene whilst northern and southern populations of the former have been separated probably since the Miocene. These patterns may represent a standard distribution trend for several other deep-sea invertebrate species with similar geographical ranges.