Since the 19th century, oceanic explorations have confirmed that the hadal zone (water depth > 6000 m) is not lifeless, but contains many fascinating organisms. Amongst them are the Mysida, which is a group of crustaceans found in many deep-sea trenches. Based on morphological observations and molecular phylogenetic analyses of an undescribed taxon within the subfamily Erythropinae, a new genus of deep-sea mysids, Xenomysis gen. n., is described from the Challenger Deep in the Mariana Trench. The new genus is not assigned to any of the tribes within the Erythropinae, as our analyses do not support the current classification scheme of Erythropinae. The result of a molecular-clock analysis with fossil calibration reveals that several groups of Mysida have independently colonized deep water habitats in different geological periods, from Triassic to Cretaceous. In addition, ancestral state reconstruction analyses indicate the degenerate eyes in both Mysidae and Petalophthalmidae is a result of parallel evolution, and the reduction of compound eyes to both "single fused eyeplate" and "two separate eyeplates" occurred multiple times independently in the evolution of Erythropinae.