Crimean-Congo hemorrhagic fever virus (CCHFV) is the most geographically widespread of the tick-borne viruses. However, African strains of CCHFV are poorly represented in sequence databases. In addition, almost all sequence data collected to date have been obtained from cases of human disease, while information regarding the circulation of the virus in tick and animal reservoirs is severely lacking. Here, we characterize the complete coding region of a novel CCHFV strain, detected in African blue ticks (Rhipicephalus (Boophilus) decoloratus) feeding on cattle in an abattoir in Kampala, Uganda. These cattle originated from a farm in Mbarara, a major cattle-trading hub for much of Uganda. Phylogenetic analysis indicates that the newly sequenced strain belongs to the African genotype II clade, which predominantly contains the sequences of strains isolated from West Africa in the 1950s, and South Africa in the 1980s. Whilst the viral S (nucleoprotein) and L (RNA polymerase) genome segments shared >90% nucleotide similarity with previously reported genotype II strains, the glycoprotein-coding M segment shared only 80% nucleotide similarity with the next most closely related strains, which were derived from ticks in Western India and Northern China. This genome segment also displayed a large number of non-synonymous mutations previously unreported in the genotype II strains. Characterization of this novel strain adds to our limited understanding of the natural diversity of CCHFV circulating in both ticks and in Africa. Such data can be used to inform the design of vaccines and diagnostics, as well as studies exploring the epidemiology and evolution of the virus for the establishment of future CCHFV control strategies.