We investigate patch selection strategies of hosts and parasitoids in heterogeneous environments. Previous theoretical work showed that when host traits vary among patches, coevolved populations of hosts and parasitoids make congruent choices (i.e., hosts and parasitoids preferentially select the same patches) and exhibit direct density dependence in the distribution of percent parasitism. However, host-parasitoid systems in the field show a range of patterns in percent parasitism, while behavioral studies indicate that hosts and parasitoids can exhibit contrary choices (i.e., hosts avoid patches favored by the parasitoid). We extend previous theory by permitting life-history traits of the parasitoid as well as the host to vary among patches. Our analysis implies that in coevolutionarily stable populations, hosts preferentially select patches that intrinsically support higher host equilibrium numbers (i.e., the equilibrium number achieved by hosts when both populations are confined to a single patch) and that parasitoids preferentially select patches that intrinsically support higher parasitoid equilibrium numbers (i.e., the equilibrium number achieved by the parasitoids when both populations are confined to a patch). Using this result, we show how variation in life-history traits among patches leads to contrary or congruent choices or leads to direct density dependence, inverse density dependence, or density independence in the distribution of percent parasitism. In addition, we determine when populations playing the coevolutionarily stable strategies are ecologically stable. Our analysis shows that heterogeneous environments containing patches where the intrinsic rate of growth of the host and the survivorship rate of the parasitoid are low result in the coevolved populations exhibiting contrary choices and, as a result, promote ecological stability.