The emergence of antibiotic-resistant bacteria in food animals is a potential public health concern. Staphylococci are a significant opportunistic pathogen both in humans and dairy cattle. In the present study, the genotypic characterization of methicillin-resistant staphylococcal strains recovered from dairy cattle in a rural community (Okada, Edo State, Nigeria) was investigated. A total of 283 samples from cattle (137 milk samples and 146 nasal swabs) were assessed between February and April 2015. Antimicrobial susceptibility was performed by Kirby-Bauer disc diffusion method. Polymerase chain reaction (PCR) assay was employed for the detection of 16S rRNA, mecA and Panton-Valentine Leucocidinis (PVL) genes. The staphylococcal strains were identified through partial 16S ribosomal ribonucleic acids (rRNA) nucleotide sequencing, and Basic Local Alignment Search Tool (BLAST) analysis of the gene sequence showed that the staphylococcal strains have 96%–100% similarity to Staphylococcus aureus (30), S. epidermidis (17), S. haemolyticus (15), S. saprophyticus (13), S. chromogenes (8), S. simulans (7), S. pseudintermedius (6) and S. xylosus (4). Resistance of 100% was observed in all Staphylococcus spp. against MET, PEN, CLN, CHL and SXT. Multi-drug resistant (MDR) bacteria from nasal cavities and raw milk reveals 13 isolates were MDR against METR, PENR, AMXR, CLNR, CHLR, SXTR CLXR, KANR, ERYR, and VANR. Of all isolates, 100% harboured the mecA gene, while 30% of the isolates possess the PVL gene. All S. aureus harboured the PVL gene while other Staphylococcus spp. were negative for the PVL gene. The presence of methicillin-resistant Staphylococcus spp. isolates in dairy cattle is a potential public health risk and thus findings in this study can be used as a baseline for further surveillance.