Bovine brucellosis due to Brucella abortus infection causes significant reproductive and production losses in cattle and is a major zoonosis. Eradication of this disease has proved difficult to achieve in Portugal where it still occurs in some regions despite an ongoing national eradication programme. In 2004, the Alentejo region, a major cattle producing area, reported one of the highest levels of bovine brucellosis in the country, especially in one divisional area. In that area, bovine brucellosis was particularly problematic in a holding of ten herds, the largest extensive cattle unit in the country, which remained infected despite an extensive test-and-slaughter programme and depopulation of five herds. A 5-year programme of RB51 vaccination with biannual test-and-slaughter was thus implemented in 2004. The apparent animal seroprevalence decreased from 19% (646/3,400) to 3% (88/2930) on the third herd-level test and remained below 0.8% (27/3324) after the fourth test. After the tenth test, the holding had a prevalence of 0.1% (2/2332) and only one herd remained positive with a within-herd prevalence of 1.1% (2/177). The results were compared to all other herds (n = 10) in the divisional area that were also persistently infected but were subject only to test-and-slaughter before being depopulated. In these herds, the strategy of test-and-slaughter did not reduce the prevalence, which remained significantly higher than the vaccinated group (median = 0.48% and 8.5% in vaccinated versus non-vaccinated herds; Wilcoxon rank sum test; P < 0.01). The success of this pilot programme in continental Portugal provided a valuable case study to the official veterinary services by illustrating the value of RB51 vaccination with parallel testing and improved biosecurity as a comprehensive and sustainable strategy for bovine brucellosis control in persistently infected herds.