Staphylococcus aureus pathogenesis is significantly influenced by the iron status of the host. However, the regulatory impact of host iron sources on S. aureus gene expression remains unknown. In this study, we combine multivariable difference gel electrophoresis and mass spectrometry with multivariate statistical analyses to systematically cluster cellular protein response across distinct iron-exposure conditions. Quadruplicate samples were simultaneously analyzed for alterations in protein abundance and/or post-translational modification state in response to environmental (iron chelation, hemin treatment) or genetic (Deltafur) alterations in bacterial iron exposure. We identified 120 proteins representing several coordinated biochemical pathways that are affected by changes in iron-exposure status. Highlighted in these experiments is the identification of the heme-regulated transport system (HrtAB), a novel transport system which plays a critical role in staphylococcal heme metabolism. Further, we show that regulated overproduction of acidic end-products brought on by iron starvation decreases local pH resulting in the release of iron from the host iron-sequestering protein transferrin. These findings reveal novel strategies used by S. aureus to acquire scarce nutrients in the hostile host environment and begin to define the iron and heme-dependent regulons of S. aureus.