Reef sharks are vulnerable predators experiencing severe population declines mainly due to overexploitation. However, beyond direct exploitation, human activities can produce indirect or sub-lethal effects such as behavioral alterations. Such alterations are well known for terrestrial fauna but poorly documented for marine species. Using an extensive sampling of 367 stereo baited underwater videos systems, we show modifications in grey reef shark (Carcharhinus amblyrhynchos) occurrence and feeding behavior along a marked gradient of isolation from humans across the New Caledonian archipelago (South-Western Pacific). The probability of occurrence decreased by 68.9% between wilderness areas (more than 25 hours travel time from the capital city) and impacted areas while the few individuals occurring in impacted areas exhibited cautious behavior. We also show that only large no-entry reserves (above 150 km²) can protect the behavior of grey reef sharks found in the wilderness. Influencing the fitness, human linked behavioral alterations should be taken into account for management strategies to ensure the persistence of populations.