This article investigates how individuals forge and maintain cooperative relationships when there is always the possibility of starting again with a new partner. The analysis shows that an ever-present opportunity to form new relationships need not destroy cooperation. Simple strategies achieve the (constrained) optimal level of cooperation. These strategies involve a “bond” in the form of reduced utility at the beginning of a relationship Two newly matched agents may have an incentive to forgo paying this bond, given that everyone else in the population requires payment of a bond to start a new relationship. This incentive disappears, however, if there is enough initial uncertainty about a new partner's valuation of future utility. Accounts from the sociological and anthropological literature indicate that individuals may indeed pay bonds to form cooperative relationships.