In order to study the relationships between mistletoes and their host species, comprehensive collections of both mistletoes and hosts are needed. The effect of sampling effort on the estimation of mistletoe host range was demonstrated in a comparison of an inventory of host mistletoe interactions published by Downey in 1998 and a 2019 inventory presented here, which is based on data from collections in the Australian Virtual Herbarium and information in the literature. New hosts were recorded for 93% of the 90 Australian mistletoes. There were 338 previously known hosts recorded to be parasitised by additional mistletoe species, and 317 new host species that were not previously known as mistletoe hosts (25 being alien species). These were from 78 new host genera and 13 new host families. The total number of host species was 1186 within 327 genera from 92 host families. A total of 63% of all Australian mistletoes parasitise species of either Eucalyptus or Acacia or both these genera. The large rise in host species recorded in less than two decades between inventories suggests that current knowledge of hosts is still incomplete, such that further new hosts will be discovered in future. Some mistletoe species show a strong preference to one host family or genus but due to insufficient collecting it is premature to conclude that any of the three species known from a single host are host specific.