Invasive species pose one of the greatest global threats to biodiversity. There has been a long history of importing coevolved natural enemies to act as biological control agents to try to suppress densities of invasive species, with historically limited success and frequent adverse impacts on native biodiversity. Our understanding of the processes and drivers of successful biological control has been focussed on invertebrates and is evidently limited and potentially ill-suited with respect to biological control of vertebrate populations. The restoration of native vertebrate predator populations provides a promising nature-based solution for slowing, halting, or even reversing the spread of some invasive vertebrates over spatial scales relevant to the management of wildlife populations. Here, we first review the growing literature and data from the pine marten-red and grey squirrel system in Europe. We synthesise a multi-decadal dataset to show that the recovery of a native predator has resulted in rapid, landscape-scale declines of an established invasive species. We then use the model system, predator–prey interaction theory, and examples from the literature to develop ecological theory relating to natural biological control in vertebrates and evolutionary processes in native-invasive predator–prey interactions. We find support for the hypotheses that evolutionary naivety of invasive species to native predators and lack of local refuges results in higher predation of naive compared to coevolved prey. We apply lessons learnt from the marten-squirrel model system to examine the plausibility of specific native predator solutions to some of the Earth's most devastating invasive vertebrates. Given the evidence, we conclude that depletion of vertebrate predator populations has increased ecosystem vulnerability to invasions and thus facilitated the spread of invasive species. Therefore, restoration of vertebrate predator populations is an underappreciated, fundamental, nature-based solution to the crisis of invasive species and should be a priority for vertebrate invasive species management globally.