The aim of the study was to assess the incidence, resistance, virulence, and genotypic characteristics of Staphylococcus spp. residing in the gastrointestinal tract of dogs and cats, as a group of animals causing potential contamination of the urban space. A high percentage of strains resistant to penicillin (58%), oxacillin (9%) and tetracycline (60%) were found. All isolates resistant to penicillin, kanamycin, or chloramphenicol carried genes responsible for individual resistance (blaZ, aph(3')-IIIa, and cat (pC194)/cat (pC223), respectively. The mecA gene was detected in 45% of the oxacillin-resistant Staphylococcus pseudintermedius strains. The amplification of DNA fragments surrounding rare restriction sites analysis demonstrated high heterogeneity of genotypic profiles correlating with phenotypic resistance profiles. Multilocus sequence typing analysis classified the methicillin-resistant S. pseudintermedius strains as ST71, ST890, and the totally new ST1047. The presence of a high level of resistance among Staphylococcus strains may suggest a potential risk of transfer of these bacteria between companion animals and humans.