The adaptation of viruses to new hosts is a poorly understood process likely involving a variety of viral structures and functions that allow efficient replication and spread. Canine parvovirus (CPV) emerged in the late 1970s as a host-range variant of a virus related to feline panleukopenia virus (FPV). Within a few years of its emergence in dogs, there was a worldwide replacement of the initial virus strain (CPV type 2) by a variant (CPV type 2a) characterized by four amino acid differences in the capsid protein. However, the evolutionary processes that underlie the acquisition of these four mutations, as well as their effects on viral fitness, both singly and in combination, are still uncertain. Using a comprehensive experimental analysis of multiple intermediate mutational combinations, we show that these four capsid mutations act in concert to alter antigenicity, cell receptor binding, and relative in vitro growth in feline cells. Hence, host adaptation involved complex interactions among both surface-exposed and buried capsid mutations that together altered cell infection and immune escape properties of the viruses. Notably, most intermediate viral genotypes containing different combinations of the four key amino acids possessed markedly lower fitness than the wild-type viruses.