This study tests an unintended benefit of a Conditional cash transfer program in Colombia: an improvement in coordination among its beneficiaries. A sample of 714 beneficiaries participate in a minimum effort coordination game. Those enrolled in the program for over a year are not just coordinating; they are more likely to exert the highest level of effort and reach higher earnings. Collected data is sufficiently rich to establish that improvement in coordination is not due to potential confounding mechanisms such as willingness to cooperate, connectivity or socio-economic characteristics. A structural choice model of the individual decision to coordinate sheds light on the role of beliefs about others’ behavior and suggests the presence of a coordination device to avoid the risk dominant equilibrium: the certainty in assessing what others might do. Participants are required to interact with local program officials, community leaders and fellow beneficiaries. We argue that this social component of the CCT changed the structure of beliefs about others’ behavior, which allowed beneficiaries to overcome coordination failures. The findings support nascent initiatives to influence beliefs through policy interventions.