Trawl surveys off Western Australia and seamounts south of New Caledonia at depths between 375 and 545 m have yielded two species of a previously unknown genus of benthic octopus (Family: Octopodidae). Histoctopus n. gen. is described here and contains two new species, Histoctopus discus and Histoctopus zipkasae n. spp. The most distinctive morphological feature of this new genus is extreme web margin development along the length of the arms, widening towards the distal tips. Of all benthic octopuses, such web margin development only occurs in this new genus and three other distinct genera, Graneledone, Pteroctopus and Velodona (from comparable depths, typically >200 m). Due to significant morphological differences between these two genera and Histoctopus, we propose that the shared web margin development reflects convergence that is peculiar to a deeper-water habitat. The function of these web extensions remains unknown; they may aid in ensnaring or enveloping prey and/or provide lift while jet swimming off the seafloor.