Human immunodeficiency virus, a primate lentivirus (PLV), causes AIDS in humans, whereas most PLVs are less or not pathogenic in monkeys. These notions suggest that the co-evolutionary process of PLVs and their hosts associates with viral pathogenicity, and therefore, that elucidating the history of virus-host co-evolution is one of the most intriguing topics in the field of virology. To address this, recent studies have focused on the interplay between intrinsic anti-viral proteins, such as tetherin, and viral antagonists. Through an experimental-phylogenetic approach, here we investigate the co-evolutionary interplay between tribe Cercopithecini tetherin and viral antagonists, Nef and Vpu. We reveal that tribe Cercopithecini tetherins are positively selected, possibly triggered by ancient Nef-like factor(s). We reconstruct the ancestral sequence of tribe Cercopithecini tetherin and demonstrate that all Nef proteins are capable of antagonizing ancestral Cercopithecini tetherin. Further, we consider the significance of evolutionary arms race between tribe Cercopithecini and their PLVs.