The broad-shouldered water-strider genus Paravelia Breddin, 1898 (Hemiptera: Heteroptera: Veliidae: Veliinae) is currently represented in Brazil by 38 species. Although the diversity of the genus in the country is relatively well known, eight states remain with no records of any species: Acre, Alagoas, Ceará (CE), Paraíba, Paraná, Pernambuco (PE), Piauí (PI), and Tocantins. Aiming to fill these gaps, several expeditions were carried out at conservation areas of the Caatinga biome between 2018 and 2021: Aiuaba Ecological Station (CE), Catimbau National Park (PE), and Serra das Confusões National Park (PI). Paravelia luisi sp. nov., a new species from PE, is described and illustrated. In addition, new records of P. bilobata Rodrigues, Moreira, Nieser, Chen & Melo, 2014, P. digitata Rodrigues & Moreira, 2016, and P. nieseri Moreira & Barbosa, 2012, and an updated key to the Brazilian species of Paravelia are provided. This study increases the number of species of Paravelia known in Brazil to 39 and provides the first records of the genus from three states: PE, with two species, and CE and PI, with one species each.