Sooty mould fungi are ubiquitous, abundant consumers of insect-honeydew that have been little-studied. They form a complex of unrelated fungi that coexist and compete for honeydew, which is a chemically complex resource. In this study, we used scanning electron microscopy in combination with T-RFLP community profiling and ITS-based tag-pyrosequencing to extensively describe the sooty mould community associated with the honeydews of two ecologically important New Zealand coelostomidiid scale insects, Coelostomidia wairoensis and Ultracoelostoma brittini. We tested the influence of host plant on the community composition of associated sooty moulds, and undertook limited analyses to examine the influence of scale insect species and geographic location. We report here a previously unknown degree of fungal diversity present in this complex, with pyrosequencing detecting on average 243 operational taxonomic units across the different sooty mould samples. In contrast, T-RFLP detected only a total of 24 different "species" (unique peaks). Nevertheless, both techniques identified similar patterns of diversity suggesting that either method is appropriate for community profiling. The composition of the microbial community associated with individual scale insect species varied although the differences may in part reflect variation in host preference and site. Scanning electron microscopy visualised an intertwined mass of fungal hyphae and fruiting bodies in near-intact physical condition, but was unable to distinguish between the different fungal communities on a morphological level, highlighting the need for molecular research. The substantial diversity revealed for the first time by pyrosequencing and our inability to identify two-thirds of the diversity to further than the fungal division highlights the significant gap in our knowledge of these fungal groups. This study provides a first extensive look at the community diversity of the fungal community closely associated with the keystone insect-honeydew systems of New Zealand's native forests and suggests there is much to learn about sooty mould communities.