BACKGROUND Tetherin is a recently identified antiviral restriction factor that restricts HIV-1 particle release in the absence of the HIV-1 viral protein U (Vpu). It is reminiscent of APOBEC3G and TRIM5a that also antagonize HIV. APOBEC3G and TRIM5a have been demonstrated to evolve under pervasive positive selection throughout primate evolution, supporting the red-queen hypothesis. Therefore, one naturally presumes that Tetherin also evolves under pervasive positive selection throughout primate evolution and supports the red-queen hypothesis. Here, we performed a detailed evolutionary analysis to address this presumption. RESULTS Results of non-synonymous and synonymous substitution rates reveal that Tetherin as a whole experiences neutral evolution rather than pervasive positive selection throughout primate evolution, as well as in non-primate mammal evolution. Sliding-window analyses show that the regions of the primate Tetherin that interact with viral proteins are under positive selection or relaxed purifying selection. In particular, the sites identified under positive selection generally focus on these regions, indicating that the main selective pressure acting on the primate Tetherin comes from virus infection. The branch-site model detected positive selection acting on the ancestral branch of the New World Monkey lineage, suggesting an episodic adaptive evolution. The positive selection was also found in duplicated Tetherins in ruminants. Moreover, there is no bias in the alterations of amino acids in the evolution of the primate Tetherin, implying that the primate Tetherin may retain broad spectrum of antiviral activity by maintaining structure stability. CONCLUSIONS These results conclude that the molecular evolution of Tetherin may be attributed to the host-virus arms race, supporting the Red Queen hypothesis, and Tetherin may be in an intermediate stage in transition from neutral to pervasive adaptive evolution.