The presence and impacts of non-indigenous species (NIS) in marine areas of high conservation or World Heritage significance have rarely been examined. Case studies worldwide suggest that the potential exists for the introduction of NIS to significantly impact conservation values in regions conserved for the uniqueness and diversity of native assemblages. In this study, a preliminary investigation was conducted to provide information essential for managing marine introductions in the Shark Bay World Heritage Property. A focused fouling plate survey sampled a total of 112 encrusting taxa, of which 10 (11.2%) were classified as introduced and 10 others as cryptogenic. Eight introduced bryozoans: Aetea anguina (Linnaeus, 1758), Bugula neritina (Linnaeus, 1758), Bugula stolonifera Ryland, 1960, Conopeum seurati (Canu, 1928), Savignyella lafontii (Audouin, 1826), Schizoporella errata (Waters, 1878), Watersipora subtorquata (d’Orbigny, 1842) and Zoobotryon verticellatum della Chiaje, 1828; one tunicate, Styela plicata Lesueur, 1823; and an introduced hydroid, Obelia dichotoma (Linnaeus, 1758) were frequent, and in some cases dominant, components of encrusting communities. Of the 20 most frequently occurring species detected in the Bay, four were introduced and of the 20 species with highest average percent cover per plate, six were introduced. At one site, space occupation by NIS averaged 71.6% ± 7.4 of plate live cover. Space occupation by an individual NIS was as high as 62.4% of plate area (mean 7.82% ± 1.8). NIS were detected at sites lacking commercial traffic and ballast water discharge and isolated by distance and physical environment, suggesting that hull fouling of recreational craft may be the most important vector in the region. Seventy-five percent of NIS detected in Shark Bay are established in Australian ports to the south of Shark Bay, while 33% are established to the north, tentatively implicating temperate affinity NIS and the movement of vessels from Australian ports south of Shark Bay as a greater risk to the region.