As human-caused extinctions and invasions accumulate across the planet, understanding the processes governing ecological functions mediated by species interactions, and anticipating the effect of species loss on such functions become increasingly urgent. In seed dispersal networks, the mechanisms that influence interaction frequencies may also influence the capacity of a species to switch to alternative partners (rewiring), influencing network robustness. Studying seed dispersal interactions in novel ecosystems on O‘ahu island, Hawai‘i, we test whether the same mechanisms defining interaction frequencies can regulate rewiring and increase network robustness to simulated species extinctions. We found that spatial and temporal overlaps were the primary mechanisms underlying interaction frequencies, and the loss of the more connected species affected networks to a greater extent. Further, rewiring increased network robustness, and morphological matching and spatial and temporal overlaps between partners were more influential on network robustness than species abundances. We argue that to achieve self-sustaining ecosystems, restoration initiatives can consider optimal morphological matching and spatial and temporal overlaps between consumers and resources to maximize chances of native plant dispersal. Specifically, restoration initiatives may benefit from replacing invasive species with native species possessing characteristics that promote frequent interactions and increase the probability of rewiring (such as long fruiting periods, small seeds and broad distributions).