Abbreviata physignathi and Spinicauda fluviatica, sp. nov., were the predominant species of nematode recovered from the gastrointestinal tracts of 65 Physignathus lesueurii examined from eastern Australia. S. fluviatica, sp. nov., is distinguished from other known species by the large well sclerotised excretory sinuses in both sexes and by the relative lengths of the spicules and gubernaculum in males. This is the first species of Spinicauda to be described from an agamid lizard. Both these nematode species occur mainly or entirely in New South Wales within 100 km of the coast; P. lesueurii is the only known host of both species. The persistence of generalised apical dentition in A. physignathi and its high host-specificity suggests a long association with this lizard, which diverged early from the main agamid stock. The significant association of these two unrelated nematode species is attributed to the high density of P. lesueurii hosts along suitable rivers. Other nematode species identified in low numbers in one or two hosts only were Abbreviata antarctica, A. confusa, Maxvachonia brygooi and immature Dracunculus sp. in the gastrointestinal tract, encysted subserosal physalopterid larvae on two stomachs, and Oswaldofilaria samfordensis in the body cavity.