The evolution of mutualisms presents a puzzle. Why does selection favour cooperation among species rather than cheaters that accept benefits but provide nothing in return? Here we present a general model that predicts three key factors will be important in mutualism evolution: (i) high benefit to cost ratio, (ii) high within-species relatedness and (iii) high between-species fidelity. These factors operate by moderating three types of feedback benefit from mutualism: cooperator association, partner-fidelity feedback and partner choice. in defining the relationship between these processes, our model also allows an assessment of their relative importance. Importantly, the model suggests that phenotypic feedbacks (partner-fidelity feedback, partner choice) are a more important explanation for between-species cooperation than the development of genetic correlations among species (cooperator association). We explain the relationship of our model to existing theories and discuss the empirical evidence for our predictions.