Four new species of Paravelia Breddin (Hemiptera: Veliidae) from Brazil are described and illustrated: Paravelia bachmanni new species and P. bromelicola new species from the states of São Paulo and Santa Catarina; P. luederwaldti new species from the state of São Paulo; and P. digitata new species from the states of Bahia and Rio Grande do Norte; totalling 61 valid species for the genus. Two of the new species (P. bachmanni and P. bromelicola) are bromeliad inhabitants, and a key to the eight bromeliadicolus species of the genus is provided. In addition, based on type material, P. amoena (Drake), P. kahli (Drake and Harris), P. nexa (Drake and Harris), and P. parilis (Drake and Harris) are re-described and illustrated. Lastly, taxonomic and distributional notes for the following species are also presented: P. basalis (Spinola), P. boliviana Breddin, P. capillata (Drake and Harris), P. cognata (Drake and Harris), P. dilatata Polhemus and Polhemus, P. foveata Polhemus and Polhemus, P. itatiayana (Drake), P. nieseri Moreira and Barbosa, P. manausana Polhemus and Polhemus, P. platensis (Berg), P. recens (Drake and Harris), and P. splendoris (Drake and Harris).