Marine conservation planning to achieve representativeness requires information on scales and sources of significant spatial variation in assemblages. Variation in reef fish assemblage structure was investigated using a nested sampling design consisting of 2 areas (separated by 10s km), 2 locations (separated by km) and 3 sites (separated by 100s m). Baited remote underwater video stations (BRUVS) were used to sample reef fish on 2 occasions (6 months apart) prior to the enforcement of the Port Stephens-Great Lakes Marine Park. Significant variation in fish assemblages was apparent at all spatial scales and these differences were consistent between times. The effect of depth was tested by comparing reef fish assemblages between 16-30 m and 40-51 m, revealing significantly different assemblage structure between depths and replicate locations within each depth (separated by kms), but not between sites. Therefore to achieve representativeness the results suggest a need to protect multiple samples of reefs covering a range of depths. BRUVS proved to be useful for sampling depths greater than typically sampled by underwater visual census and provided relative abundance estimates of a wide range of species including commercially and recreationally targeted reef fish that are expected to show the greatest response to marine park zoning.