The number of Marine Protected Areas (MPAs) has increased globally as concerns over the impact that human activities are having on the world’s oceans have also increased. Monitoring is a key requirement to determine if MPAs are meeting their objectives. However, many recently declared MPA’s are large, offshore, or form part of an expansive network and spatial information about the habitats, communities and species that they contain is often lacking. This presents challenges for deciding exactly what to monitor and developing strategies on how to monitor it efficiently. Here we examine these issues using the Flinders Marine Park in Australia as a case study. We trial a two-stage version of a spatially-balanced, probabilistic sampling design combined with Baited Remote Underwater Videos (BRUVs) to perform an initial inventory, and we evaluate the potential of six commercially and ecologically important demersal fish as indicators within the Marine Park. Using this approach we were able to (1) quantitatively describe the distribution of the fish species in the Marine Park; (2) establish quantitative and representative estimates of their abundance throughout the Marine Park to serve as a baseline for future monitoring; (3) conduct power analyses to estimate the magnitude of increase we may be able to detect with feasible levels of sampling effort. Power analysis suggested that for most of our potential indicator species, detecting increases in abundance as small as 50% from present values should be feasible if sampling is restricted to a species’ preferred habitat and the same sites are sampled through time. Our approach is transferrable to other regions where monitoring programs must be designed based on limited spatial and biological data, assisting with decisions on what and how to monitor.