A new species of Leptophoxoides Barnard, 1962 is described with material from the continental slope of Rio Grande do Norte state, northeastern Brazil at three different depths: 150, 400 and 2,500 meters. Leptophoxoides longisetae sp. nov. can be diagnosed and distinguished from the other two species of the genus, L. molaris Barnard, 1962 and L. marina Senna, 2010, by the following characters: antenna 1 peduncular article 1 ventral apex weakly ensiform; maxilla 1 inner plate longer than outer; maxilliped palp article 3 with blunt and extremely protuberant apex; gnathopods 1-2 carpus almost cryptic; gnathopod 2 palm defined by a large and sharply produced palmar hump; pereopod 6 basis posterodistal corner produced as a blunt lobe; and telson with two dorsal long plumose setae on each side. This is the first record of the genus for northeastern Brazilian waters, uncovering a higher biodiversity in deep waters.