Around the second century BC Teos received grants of asylia from a large number of Cretan cities. This article examines the context of the Tean request for asylia as well as the different levels of compliance inherent in the responses. In these negotiations the Teans aimed to promote their own protection, while the Cretans applied a strategy that aimed at keeping the options for predatory warfare open. This eventually led to new negotiations where the Teans requested to have their former attacker as a military ally and protector. The article points to violence as a legitimate mode of production and to the documents analysed here as a bridge between violence and protection. An appendix is included of Cretan grants of asylia during the Hellenistic period.