The Indo-Papuan family Velocipedidae Bergroth, 1891 (Heteroptera) is revised; a new genus, 19 new species and four new subspecies are described. Costomedes gen. nov. (type species: C. gressitti spec. nov.) comprises 11 new species: C. cheesmanae from New Guinea, C. fakfakensis from New Guinea, C. gazelle from New Britain and Bismarck Archipelago, C. gressitti from New Guinea, C. heissi from Ceram, C. hirsutus from New Guinea, C. karimui from New Guinea (including one new subspecies: C. karimui eliptamin from New Guinea), C. morobensis from New Guinea, C. sedlaceki from New Guinea, C. solomonensis from the Solomon Islands and C. toxopeusi from New Guinea. The following eight new species are described in the genus Scotomedes Stål, 1873: S. distanti from Myanmar, S. gedehensis from Java, S. lemoulti from Vietnam, S. maai from South China (Fukien (Fujian)), S. polis from Philippines (Luzon), S. rudolfifrom West Malaysia, S. sumatrensis from Indonesia (Sumatra), S. thai from Thailand and India (Sikkim). In addition three new subspecies are described: S. alienus sikkimensis from India (Sikkim), S. ater confrater from East Malaysia (Sabah, Borneo), and S. priscus jacobsoni from Indonesia (Sumatra). Lectotypes are designated for Godefridus alienus Distant, 1904, and for Velocipeda prisca Bergroth 1891, to promote stability of nomenclature. The type specimens of Velocipeda minor Breddin, 1903 and Velocipeda biguttulata Reuter, 1908 could not be located.