We present a mathematical model of coevolutionary interactions between partners in a coral-algae mutualistic symbiosis. Our goal is to better understand factors affecting the potential evolution of bleaching resistance in corals in response to increased average sea temperatures. We explore the evolutionary consequences of four factors: (i) trade-offs among fitness components, (ii) different proximate mechanisms of coral bleaching, (iii) the genetic determination of bleaching resistance, and (iv) the mode of sexual reproduction. We show that traits in mutualistic symbioses, such as thermal tolerance in corals, are potentially subject to novel kinds of evolutionary constraints and that these constraints are mediated by ecological dynamics. We also show that some proximate mechanisms of bleaching yield faster evolutionary responses to temperature stress and that the nature of interspecific control of bleaching resistance and the mode of sexual reproduction interact to strongly influence the rate of spread of resistance alleles. These qualitative theoretical results highlight important future directions for empirical research in order to quantify the potential for coral reefs to evolve resistance to thermal stress.