Context: Seascape connectivity refers to how the spatial configuration of marine habitats facilitates or hinders the movement of organisms, nutrients, materials or energy. Predicting and ranking potential connectivity among habitat patches for coral reef fishes helps to understand how reef fishes could utilize and connect multiple habitat types through the flow of nutrients, energy and biomass across the wider seascape during foraging movements. Objectives: To advance a spatially explicit understanding of connectivity linkages within a tropical atoll system by modeling, mapping and quantifying potential seascape connectivity for two locally abundant herbivorous reef fish species, the parrotfish, Chlorurus spilurus (pahoro hohoni or pa’ati pa’apa’a auahi), and the surgeonfish, Acanthurus triostegus (manini). Methods: We applied a two-step modeling approach by first mapping habitat suitability for the focal species. A graph-theoretic modeling technique was then applied to model and measure the contribution of benthic habitat patches to species-specific potential connectivity within the seascape. Results: Habitat suitability was higher and less fragmented for C. spilurus than for A. triostegus. Potential ecological connectivity estimates for C. spilurus were higher across the entire seascape, with differences between species likely driven by local-scale benthic habitat patch configuration and species home ranges. Hotspots of ecological connectivity across the atoll were mapped for both species. Conclusions: Despite advances in the application of graph-theoretic techniques in the coastal environment, few marine conservation and restoration measures currently integrate spatial information on ecological connectivity. This two-step spatial modeling approach holds great potential for rapid application of connectivity modeling at multiple spatial scales, which may predict ecological responses to conservation actions including active habitat restoration.