A new species of Apseudidae is described from a submarine canyon in the Mediterranean Sea, Leviapseudes tethys sp. nov. The species was sampled at 600 m depth on deep muddy sand. The new species is characterized by the presence of processes on both sides of the rostrum, a pinnate seta on the inner distal margin of the maxillipedal endite, smooth distal spines of the labium palp, two spines on the cheliped basis, three ventral spines on pereopod 1 basis and an unarticulated pleopod exopod. This is the second species and the third record of the genus in the Mediterranean Sea, and raises the number of tanaid species known from the deep Mediterranean Sea to a total of 16. The diagnosis of the genus is amended in light of the new data and re-evaluation of previous works. The new species presents a set of characters that provide novel insights to understanding the diversity and taxonomy of the Leviapseudinae, as well as their geographic distribution. Finally, a list of all deep-sea Tanaidacea known in the Mediterranean Sea is provided.