Several billion Facebook messages are sent every day. While there are many solutions to email security whose usability has been extensively studied, little work has been done in the area of message security for Facebook and even less on the usability aspects in this area. To evaluate the need for such a mechanism, we conducted a screening study with 514 participants, which showed a clear desire to protect private messages on Facebook. We therefore proceeded to analyse the usability of existing approaches and extracted key design decisions for further evaluation. Based on this analysis, we conducted a laboratory study with 96 participants to analyse different usability aspects and requirements of a Facebook message encryption mechanism. Two key findings of our study are that automatic key management and key recovery capabilities are important features for such a mechanism. Following on from these studies, we designed and implemented a usable service-based encryption mechanism for Facebook conversations. In a final study with 15 participants, we analysed the usability of our solution. All participants were capable of successfully encrypting their Facebook conversations without error when using our service, and the mechanism was perceived as usable and useful. The results of our work suggest that in the context of the social web, new security/usability trade-offs can be explored to protect users more effectively.