In veterinary medicine, Staphylococcus aureus is associated with a range of mild to severe infections. The high density of livestock in intensive farming systems increases the risk of disease spread and hampers its control and measures of prevention, making S. aureus one of the most important animal pathogens. Multiple-locus variable-number tandem repeat fingerprinting (MLVF) has been successfully applied to the characterization of livestock-associated meticillin-resistant Staphylococcus aureus (MRSA) ST398 but not to the characterization of a wide range of other animal isolates. The objective of the current study was to examine the effectiveness of MLVF for studying S. aureus strains isolated from households, farms and exotic animals in three regions of Poland. MLVF, random amplification of polymorphic DNA (RAPD), spa typing and diagnostic microarrays were compared to determine the most suitable combination of methods for veterinary purposes. MLVF generated results consistent with host and geographic origins, reflecting population structures with a high concordance to spa typing results. MLVF has been proven to be a rapid, highly discriminatory and cost-effective method suitable for molecular typing in veterinary settings.