Mammalian genes and genomes have been shaped by ancient and ongoing challenges from viruses. These genetic imprints can be identified via evolutionary analyses to reveal fundamental details about when (how old), where (which protein domains), and how (what are the functional consequences of adaptive changes) host-virus arms races alter the proteins involved. Just as extreme amino acid conservation can serve to identify key immutable residues in enzymes, positively selected residues point to molecular recognition interfaces between host and viral proteins that have adapted and counter-adapted in a long series of classical Red Queen conflicts. Common rules for the strategies employed by both hosts and viruses have emerged from case studies of innate immunity genes in primates. We are now poised to use these rules to transition from a retrospective view of host-virus arms races to specific predictions about which host genes face pathogen antagonism and how those genetic conflicts transform host and virus evolution.