Rabies causes more than 24 000 human deaths annually in Sub-Saharan Africa. The World Health Organization recommends annual canine vaccination campaigns with at least 70% coverage to control the disease. While previous studies have considered optimal coverage of animal rabies vaccination, variation in the frequency of vaccination campaigns has not been explored. To evaluate the cost-effectiveness of rabies canine vaccination campaigns at varying coverage and frequency, we parametrized a rabies virus transmission model to two districts of northwest Tanzania, Ngorongoro (pastoral) and Serengeti (agro-pastoral). We found that optimal vaccination strategies were every 2 years, at 80% coverage in Ngorongoro and annually at 70% coverage in Serengeti. We further found that the optimality of these strategies was sensitive to the rate of rabies reintroduction from outside the district. Specifically, if a geographically coordinated campaign could reduce reintroduction, vaccination campaigns every 2 years could effectively manage rabies in both districts. Thus, coordinated campaigns may provide monetary savings in addition to public health benefits. Our results indicate that frequency and coverage of canine vaccination campaigns should be evaluated simultaneously and tailored to local canine ecology as well as to the risk of disease reintroduction from surrounding regions.