Antibiotic- and heat-resistant bacteria in camel milk is a potential public health problem. Staphylococcus aureus (S. aureus) is an opportunistic pathogen in humans, dairy cattle and camels. We characterized the phenotype and genotype of methicillin-resistant staphylococcal strains recovered from pasteurized and raw camel milk (as control) distributed in the retail markets of Saudi Arabia. Of the 100 samples assessed between March and May 2016, 20 S. aureus isolates were recovered from pasteurized milk, 10 of which were resistant to cefoxitin, and as such, were methicillin-resistant. However, raw camel milk did not contain methicillin-resistant S. aureus (MRSA). Antimicrobial susceptibility tests showed that the resistance ratio for other antibiotics was 60%. We performed a polymerase chain reaction (PCR) assay using primers for the methicillin-resistant gene mecA and nucleotide sequencing to detect and verify the methicillin-resistant strains. Basic local alignment search tool (BLAST) analysis of the gene sequences showed a 96-100% similarity between the resistant isolates and the S. aureus CS100 strain's mecA gene. Ten of the methicillin-resistant isolates were heat-resistant and were stable at temperatures up to 85°C for 60 s, and three of these were resistant at 90°C for 60 or 90 s. The mean decimal reduction time (D85-value) was 111 s for the ten isolates. Sodium dodecyl sulfate (SDS)/polyacrylamide gel electrophoresis (PAGE) showed that there was no difference in the total protein profiles for the ten methicillin heat-resistant S. aureus (MHRSA) isolates and for S. aureus ATCC 29737. In conclusion, a relatively high percentage of the tested pasteurized camel milk samples contained S. aureus (20%) and MHRSA (10%).