Bovine tuberculosis (bTB) caused by Mycobacterium bovis is an important re-emerging disease affecting livestock, wildlife and humans. Epidemiological studies are crucial to identifying the source of bTB infection, and its transmission dynamics and host preference, and thus to the implementation of effective strategies to contain it. In this study, we typed M. bovis isolates from livestock, and investigated their genetic diversity and distribution. A total of 204 M. bovis isolates were collected from cattle (n = 164) and Sicilian black pigs (n = 40) reared in a limited area of the province of Messina, northeastern Sicily, an area that had previously been identified as having the highest incidence of bTB in livestock on the island. All M. bovis isolates were typed by both spoligotyping and 12-loci MIRU-VNTR analysis. Results from both methods were then combined in order to improve the discriminatory power of M. bovis typing. We identified 73 combined genetic profiles. Thirty-five point six percent of the profiles were common to at least two animals, whereas 64.4% of profiles occurred in only one animal. A number of genetic profiles were predominant in either cattle or black pigs. We identified common genetic patterns in M. bovis isolates originating not only from neighboring districts, but also from non-neighboring districts. Our findings suggest that bTB is widespread in our setting, and is caused by a large number of genetically diverse M. bovis strains. The ecology and farming practices characteristic of the area may explain the substantial M. bovis heterogeneity observed, and could represent obstacles to bTB eradication.