Gerromorpha Popov, 1971 is a fascinating and diverse insect lineage that evolved about 200 Mya to spend their entire life cycle on the air–water interface and have since colonized all types of aquatic habitats. The subfamily Halobatinae Bianchi, 1896 is particularly interesting because some species have adapted to life on the open ocean—a habitat where insects are very rarely found. Several attempts have been made to reconstruct the phylogenetic hypotheses of this subfamily, but the use of a few partial gene sequences recovered only a handful of well-supported relationships, thus limiting evolutionary inferences. Fortunately, the emergence of high-throughput sequencing technologies has enabled the recovery of more genetic markers for phylogenetic inference. We applied genome skimming to obtain mitochondrial and nuclear genes from low-coverage whole-genome sequencing of 85 specimens for reconstructing a well-supported phylogeny, with particular emphasis on Halobatinae. Our study confirmed that Metrocorini Matsuda, 1960, is paraphyletic, whereas Esakia Lundblad, 1933, and Ventidius Distant, 1910, are more closely related to Halobatini Bianchi, 1896, than Metrocoris Mayr, 1865, and Eurymetra Esaki, 1926. We also found that Ventidius is paraphyletic and in need of a taxonomic revision. Ancestral state reconstruction suggests that Halobatinae evolved progressively from limnic to coastal habitats, eventually attaining a marine lifestyle, especially in the genus Halobates Eschscholtz, 1822, where the oceanic lifestyle evolved thrice. Our results demonstrate that genome skimming is a powerful and straightforward approach to recover genetic loci for robust phylogenetic analysis in non-model insects.