Bovine brucellosis is a zoonotic disease of global public health and economic importance. South Africa has had a national bovine brucellosis eradication scheme since 1979; however, no published report on elimination progress from any province exists. We analysed laboratory test results of all cattle herds participating in the Gauteng Provincial Veterinary Services’ eradication scheme between 2013 and 2018. Herd reactor status and within-herd seroprevalence, modelled using mixed-effects logistic and negative binomial regression models, respectively, showed no significant change over the period. However, provincial State Vet Areas, Randfontein (OR = 1.6; 95% CI: 1.2–2.1; p < 0.001) and Germiston (OR = 1.9; 95% CI: 1.5–2.5, p = 0.008) had higher odds of reactor herds than the Pretoria Area and within-herd prevalence count ratios for these areas were 1.5-fold greater than the Pretoria State Vet Area (p < 0.001). Reactor herds were associated with increased herd size (p < 0.001) and larger herd sizes were associated with lower within-herd prevalence (p < 0.001). Despite no evidence of significant progress toward bovine brucellosis elimination in Gauteng province, variability in bovine brucellosis prevalence between State Vet Areas exists. A public health and farmer-supported strategy of ongoing district-based surveillance and cattle vaccination targeting small- to medium-sized herds combined with compulsory test and slaughter of reactors in larger herds is recommended for the province.