A new giant species of the subfamily Rhynchoproctinae with strikingly bi-coloured, red-yellow legs contrasting with a black body is described: Alienostreptus bicoloripes sp. nov. from Vietnam. The new species is assigned to the genus Alienostreptus Pimvichai, Enghoff & Panha, 2010 hitherto comprising one species, A. alienus (Attems, 1936), and differing from other rhynchoproctine genera by having the femoral spine duplicated. Species of this genus share three synapomorphic characters of the subfamily, viz (1) anterior coxal fold forms deep concavity in posterior view, (2) posterior coxal fold very low, and (3) posterior coxal fold with mesal flap. A superficially very similar colourful species from Borneo, also with bi-coloured legs but clearly not belonging to Alienostreptus due to the position of ventral soft pads on male legs, is documented based on photographs.