African swine fever (ASF) is a highly lethal and economically significant disease of domestic pigs in the southern African sub-region, where outbreaks regularly occur. There is anecdotal evidence suggesting that trans-boundary movement of infected animals may have played a role in precipitating widespread outbreaks in the past, however, since the 1970s outbreaks have generally been more localised, particularly in those countries where control of animal movement is strictly regulated. The origin and relatedness of regional ASF outbreaks was investigated here by means of a two-step genetic characterisation approach whereby p72 gene sequencing was used to delineate genotypes, prior to intra-genotypic resolution of viral relationships by central variable region (CVR) characterisation of the 9RL ORF. In this manner, regional virus heterogeneity and epidemiological links between outbreaks could be assessed for the first time through phylogenetic analysis of the C-terminal end of the p72 gene of viruses recovered from domestic pig outbreaks in southern Africa between 1973 and 1999. The phylogeny revealed the presence of 14 distinct p72 genotypes of which 6 (genotypes XVII–XXII) were considered novel. Eight of these were country-specific with the remaining six having a trans-boundary distribution. CVR products were heterogeneous in size ranging from 377 bp to 533 bp across the 14 southern African genotypes. Within-genotype CVR comparisons revealed the presence of a genotype XIX virus with an extended field presence in South Africa (1985–1996) and permitted discrimination between three genotype VII viruses that were identical across the p72 gene.