Two species of Deretrema (Zoogonidae) are reported from labrid fishes from the Great Barrier Reef. D. nahaense Yamaguti, 1942 is recorded from the gall-bladders of the labrids Thalassoma hardwicke (Bennett), T. jansenii (Bleeker), T. lunare (Linnaeus) and T. lutescens (Lay & Bennett). This species is recognised, despite having been formerly synonymised with D. pacificum Yamaguti, 1942. In addition to morphological distinction, D. nahaense appears to have strict host-specificity for the genus Thalassoma. D. woolcockae n.sp. is described from the gallbladder of Hemigymnus fasciatus (Bloch). The new species is close to D. acutum Pritchard, 1963 and D. plotosi Yamaguti, 1940, but differs slightly in the distribution of the vitelline follicles, the sucker-ratio and the position of the cirrus-sac. In addition, this species also appears to have a distinct host-specificity, being restricted to one labrid species.