The introduction of exotic predators into new areas has had significant impacts on naïve prey species, which initially lack behavioural mechanisms to avoid predation. Understanding a species' ability to respond appropriately to novel threats may inform in situ management options for threatened island populations. In the presence of nest predators, physical characteristics of the nest site can influence the likelihood that eggs or chicks are lost to predation. Some birds that evolved under high nest predation pressure show predictable changes in nest-site selection following nest predation, but the ability of naïve island birds to alter nest-site decisions based on experience with novel nest predators has not been well studied. We examined nest-site choices of re-nesting Chatham Island black robins Petroica traversi following nest predation by invasive European starlings Sturnus vulgaris. Robins whose first nests were depredated re-nested in a new location that was significantly lower to the ground than pairs whose first nests were lost through other causes. As predation risk increases with nest height, the lower placement of re-nests is consistent with a movement towards safer nest sites. The cause of nest failure did not influence the choice of substrate for a replacement nest, nor did individual pairs re-nest further away from depredated nests. Changes in nest-site selection did not carry over into subsequent nesting seasons. Our results suggest that some evolutionarily naïve species may be capable of assessing immediate risk through individual experience with novel predators, and modifying their nest-site decisions accordingly.