Because herbivory is a critical component of resilient reefs, there is a need to investigate the dynamics of herbivorous fish assemblages over various spatiotemporal scales. During the period of 2011–2019, 483 belt transect surveys were conducted across 26 sites around New Providence to assess the status of parrotfish populations across different reefs. Non-metric multidimensional scaling revealed two distinct parrotfish assemblages around New Providence temporally, differing between 2019 and earlier surveys, and spatially between fore and patch reef zones. Temporal analysis showed a significant decrease (59%) in parrotfish densities across reef sites and significant changes in mean density over time for three species Scarus iseri, Sparisoma aurofrenatum and Sp. atomarium. Changes in the size frequency distribution of parrotfish—particularly reductions in individuals ≥31 cm in size and the complete loss of fish >40 cm across all sites were found. Interactions between reef zone and size class were significant with the greater frequencies of larger individuals (≥21 cm) driving patterns (positive associations) on forereefs. These patterns also appear to be partly driven by variability in the abundance and size composition of Sparisoma viride, which is one of the species primarily targeted by Bahamian fishers, as well as one of the most common parrotfish across reef zones.