The new genus Altavelia Polhemus & Moreira (Heteroptera: Gerromorpha: Veliidae) includes seven species previously contained in the inveruglas group of Paravelia Breddin, 1898 and four new species from Colombia: A. altoandina Molano & Morales, A. antioquia Molano & Morales, A. montana Molano & Morales, and A. quindiana Molano & Morales. Additionally, A. amoena (Drake, 1957) is synonymized with A. flavomarginata (Hungerford, 1930). The genus is characterized by prominent setal tufts or sclerotized wing-like processes on the male proctiger; elongate body shape with long, slender legs; uniformly blackish forewings; antennal segment I longest; and the female abdomen with tergum VIII deflexed. Species in this genus occur at high elevations in the Andes Mountains with records from 1500 to 3600 m. A key is provided to all 11 species in the genus and new distributional records are presented for A. boliviana (Breddin, 1898), A. columbiensis (Hungerford, 1930), and A. flavomarginata.