In this paper, we investigate the epidemiology of infections-associated Staphylococcusaureus (S. aureus) from the Medical Intensive Care Unit (MICU) at University Hospital Center of Constantine (UHCC) in Algeria, with a special emphasis on methicillin-resistant strains (MRSA) revealed by cefoxitin disks (30 μg), then confirmed by penicillin-binding protein (PBP2a) agglutination and real-time polymerase chain reaction (RT-PCR) targeting mecA and mecC genes. Staphylococcal Cassette Chromosome mec (SCCmec type), staphylococcal protein A (spa-type), multilocus sequence type (MLST), Panton–Valentine Leucocidin (PVL), and toxic shock syndrome toxin-1 (TSST-1) were further investigated in all isolates, and whole genome sequencing was performed for a selected subset of three hospital-acquired MRSA (HA-MRSA) isolates. A measurement of 80% out of the 50 S. aureus isolates were identified as HA-MRSA harbouring the mecA gene, and 72.5% of them were multidrug resistant (MDR). Twelve STs, four different SCCmec cassettes, fourteen spa types, ten isolates Panton–Valentine Leukocidin (PVL)-positive, and three isolates TSST-1 were identified. Interestingly, there was a high prevalence (n = 29; 72.5%) of a worrisome emerging clone: the HA-MRSA ST239/241 SCCmec-III mercury with PVL negative, resistant to β-lactams, aminoglycosides, quinolones, and tetracyclines. Other clones of HA-MRSA isolates were also identified, including PVL-positive ST80 SCCmec-IV/SCCmec-unknown (22.5%), ST34 SCCmec-V with TSST-1 positive (2.5%), and PVL-negative ST72 SCCmec-II (2.5%). Genome analysis enables us to describe the first detection of both PVL-negative HA-MRSA ST239/241 SCCmec-III mercury carrying ccrC, as well as SCCmec-V cassette, which dramatically changes the epidemiology of S. aureus infections in one of the hospitals in eastern Algeria.