Exotic predators contribute to novel ecological situations for native prey species, particularly when prey exhibit behaviors that are maladaptive in the presence of novel predators. In these instances, predators may drive selection because prey with naïve behavioral or morphological traits experience reduced survival and/or reproductive fitness. Islands are homes to many endemic species that are often exposed to exotic predation pressure from accidental or intentional predator colonisation. Many island endemics respond positively to predator eradication, but we are unaware of any examples of rapid numerical and behavioral responses to predator removal. The Key Largo woodrat (Neotoma floridana smalli) was historically reduced to a small population as evidenced by the rarity of their characteristic stick-nests and few captures. We monitored woodrats at supplemental nests for two years during a time when exotic predators were removed from Crocodile Lake National Wildlife Refuge. We used multi-state dynamic occupancy models to evaluate changes in woodrat distribution and stick-nest building behavior in response to predator removal. The distribution of woodrats at supplemental nests increased from < 25% to nearly 50% in the two-year period. Furthermore, woodrats commonly built stick-nests on top of supplemental nests post-predator removal, which followed a gradient away from areas with source domestic cat populations and individual pythons. We suggest that stick-nest building is maladaptive in the presence of novel predators, which has implications for trophic cascades because woodrats are ecosystem engineers, providing refugia for other species, concentrating woody vegetation for decomposition, and dispersing seeds on the island of Key Largo.