Zoarcid fishes of the genus Gymnelus Reinhardt inhabit the shelves of the North Pacific Ocean and the Arctic. A new species, G. pseudosquamatus sp. nov., is described from trawl samples taken at depths off South-West Greenland. It is most similar to the type species of the genus, Common Fish Doctor G. viridis, inhabiting the coastal waters of Greenland. The characters of the latter are specified on materials from the type locality, including the neotype and specimens of J.C.H. Reinhardt. Both species are in the group of Gymnelus with an interrupted supratemporal commissura, two supratemporal sensory pores (1+0+1), and a dorsal fin originating above the pectoral fin. The two species differ in a complex of characters, including habitus. In G. viridis, the trunk is roundish in cross section, highest above the beginning of the anal fin; the anterior rays of the dorsal fin are shortened, and covered with a thick and somewhat fleshy skin. In G. pseudosquamatus, the body is compressed and deeper anteriorly, the dorsal-fin rays are evenly elongated, and the fin membrane is thin. Differences in counts and measurements are statistically significant, including the number of vertebrae and rays in the dorsal, anal and pectoral fins, the number of teeth on the jaws, as well as the length and depth of the head, predorsal length, the length of pectoral fins, eye diameter and length of the gill slit. The color of G. pseudosquamatus, with 8–16 wide brown mottled bands, is also unusual, as the skin is dotted with light speckles that create the illusion of tiny scales, which is the reason for the name “pseudosquamatus”, the Deceptive Fish Doctor. While G. viridis is found inshore in a zone of macroalgae, the new species is found in deeper waters (100–457 m) along the shelf edge of South-West Greenland. The name Ophidium stigma Lay et Bennett, 1839 (=Gymnelus stigma) should be excluded from the synonymy of G. viridis, since the original description mentions the presence of scales on the body, which are absent in Gymnelus.