Research on outsourcing governance has focused on two modes: formal governance based on a legally binding contract, and relational governance based on a psychological contract between the vendor’s relationship manager and the client’s project manager. Some researchers argue that the two forms of governance are substitutes for each other. Others model them as complements. Here, we find empirical support for the complementary model and extend it to explain the sequential relationship between formal and relational governance, with relational governance mediating the effect of formal governance on BPO performance. The formal contract is the initial and necessary platform for the outsourcing relationship. If it is well structured, it shapes a good outsourcing relationship, which then supports high BPO performance. The mediated relationship between formal and relational governance extends theory and prior research, which focused on either a substitutive or a complementary relationship between the two forms of governance.