A new species of deep-reef fish in the goby genus Palatogobius is described from recent submersible collections off Curaçao and Dominica. Video footage of schools of this species reveal predation by the invasive Indo-Pacific lionfish (Pterois spp.), the first record of undescribed fauna potentially being eaten by lionfish outside of its native range. We present molecular phylogenetic data for all valid species of Palatogobius and related genera, as well as a taxonomic key to the species of Palatogobius and a generic key to Palatogobius and related genera in the western Atlantic. Lastly, we discuss ecological and behavioral aspects of some deep-reef fishes in light of potential threats from invasive lionfish.