Impacts of climate change on organisms are already apparent, with effects ranging from the individual to ecosystem scales. For organisms engaged in mutualisms, climate may affect population performance directly or indirectly through mediated effects on their mutualists. We tested this hypothesis for two stink bugs, Acrosternum hilare and Murgantia histrionica, and their gut-associated symbionts. We reared these species at two constant temperatures, 25 and 30 degrees C, and monitored population demographic parameters and the presence of gut-associated symbionts with diagnostic PCR primer sets. Both stink bugs lost their respective gut symbionts within two generations at 30 degrees C. In addition, the insect survivorship and reproductive rates of both A. hilare and M. histrionica at 30 degrees C were lower than at 25 degrees C. Other demographic parameters also indicated a decrease in overall insect fitness at the high temperature. Collectively our data showed that the decrease in host fitness was coupled with, and potentially mediated by, symbiont loss at 30 degrees C. This work illustrates the need to better understand the biology of animal-symbiont associations and the consequences of local climate for the dynamics of these interactions.