The public health crisis of antibiotic resistance has spurred studies of nonconventional antimicrobial approaches. Gallium is a promising and emerging approach to treating multidrug-resistant bacteria via a Trojan horse-like antimicrobial strategy or the physical disruption of bacterial activity. This study utilized experimental evolution to test the evolvability of gallium resistance in Staphylococcus aureus and potential correlated traits in metals, antibiotics, and polyfluorinated compounds and their genomics foundations. Whole-genome sequencing was utilized to reveal the functional networks of mutations associated with gallium resistance. Additionally, scanning electron microscopy (SEM) observation was used to visualize the distinct morphological changes on the surface of the gallium-resistant populations and compared to the control populations. As demonstrated by these studies, S. aureus evolved resistance to gallium after 20 days of selection. Furthermore, these populations displayed correlated traits to heavy metals, and polyfluorinated compounds. In contrast, the gallium-resistant populations were very sensitive to antibiotics. Whole-genome analysis revealed significant polymorphisms in the gallium (III)-resistant populations including, staphyloferrinA export MFS transporter/D ornithine citrate ligase (sfaA/sfaD), teichoic acid D Ala esterase (fmtA), DUF3169 family protein (KQ76_RS01520), and adenine phosphoribosyltransferase (KQ76_RS08360), while the following polymorphisms in ABC transporter permease subunit (pstC) and acyltransferase family protein (KQ76_RS04365) were unique to the control populations. Polymorphisms directly affected the cell’s morphology. SEM images showed significant external ultrastructural changes in the gallium-selected bacterial cells compared to the control cells. Our study confirmed that using gallium as antimicrobials can have significant health and environmental implications.