Austrovelia, gen. nov. (type-species A. queenslandica, sp. nov., from North Queensland), A. caledonica, sp. nov. (from New Caledonia), and Phrynovelia caledonica, sp. nov., and P. bimaculata, sp. nov. (both from New Caledonia) are described and compared with related known genera and species. Altitudinal distribution of A, queenslandica and biogeographic affinities between New Caledonia and the Mount Sorrow tableland in North Queensland are discussed, and a generalized distribution of terrestrial Mesoveliidae in the south-west Pacific is given.