Shipwrecks can have significant localized effects when grounded on shallow coral reefs. These effects are not limited to the immediate physical damage, but can have wide-spread and lasting impacts due to alteration of the chemical makeup of the surrounding water column. This can subsequently impact the growth of benthic organisms, often leading to phase shifts and high levels of mortality of corals in the vicinity of the wreck. At Palmyra atoll, the grounding of a longline fishing vessel on the shallow reef terrace is associated with a phase shift to the corallimorph, Rhodactis howesii. In 2013, a wreck removal effort initiated by the US Department of Fish and Wildlife resulted in the successful extraction and disposal of the wreckage, after which the density and percent cover of R. howesii in the immediate vicinity of the wreck site dropped precipitously. Here, we document the response of the fish community to the wreck removal and localized decline in R. howesii. We show that the biomass of scarid parrotfishes and acanthurid surgeonfishes and unicornfishes (primarily herbivores) increased after the removal of the wreck, while biomass of chaetodontid butterflyfishes (primarily invertivores, many species are known to feed on coelenterate polyps) declined over the study period. The density of small scarids and acanthurids also increased, but only after a few years post removal. Overall these results indicate that Palmyra’s unfished herbivore population has rapidly responded to the removal of the wreck and associated decrease in corallimorph cover, can maintain high levels of grazing where space is made available for colonization of early successional algae species, and may have the potential to facilitate reef recovery.