Mathematical models of the coevolutionary process have uncovered consequences of host-parasite interactions that go well beyond the traditional realm of the Red Queen, potentially explaining several important evolutionary transitions. However, these models also demonstrate that the specific consequences of coevolution are sensitive to the structure of the infection matrix, which is embedded in models to describe the likelihood of infection in encounters between specific host and parasite genotypes. Traditional cross-infection approaches to estimating infection matrices might be unreliable because evolutionary dynamics and experimental sampling lead to missing genotypes. Consequently, our goal is to identify the likely structure of infection matrices by synthesizing molecular mechanisms of host immune defense and parasite counterdefense with coevolutionary models. This synthesis reveals that the molecular mechanisms of immune reactions, although complex and diverse, conform to two basic models commonly used within coevolutionary theory: matching infection and targeted recognition. Our synthesis also overturns conventional wisdom, revealing that the general models are not taxonomically restricted but are applicable to plants, invertebrates, and vertebrates. Finally, our synthesis identifies several important areas for future research that should improve the explanatory power of coevolutionary models. The most important among these include empirical studies to identify the molecular hotspots of genotypic specificity and theoretical studies examining the consequences of matrices that more accurately represent multistep infection processes and quantitative defenses.