Benthic monitoring of the marine shallow bottoms off Menorca (Balearic Islands, western Mediterranean) has yielded several specimens of the leptostracan genus Paranebalia Claus, 1880. This finding constitutes the first report of the genus from European latitudes and the Mediterranean Sea and therefore the third leptostracan genus known from the Mediterranean. Specimens are described, illustrated and compared to other known species; they might represent a new species but their state of maturity and the lack of an appropriate diagnosis for the type species of the genus, Paranebalia longipes (Willemöes-Suhm, 1875), did not allow to confirm its taxonomic status.