Sexual conflict is thought to be a significant driving force in the evolution of sexual dimorphism, and underpins the sexually dimorphic grasping and anti-grasping structures found in many water strider species (Gerridae). By examining video recordings of premating struggles in the Australian riffle bug genus Austromicrovelia, we show that as in the gerrids, the Veliidae may face similar selective pressures, which may lead to conflict between the sexes. From our video recordings we identify putative male and female conflict traits that interact with one another and are thus predicted to coevolve. We then use phylogenetic comparative methods to test for patterns of male and female coevolution, which are consistent with a sexually antagonistic arms race.