The relationship between composition and plasmonic properties in noble metal nanoalloys is still largely unexplored. Yet, nanoalloys of noble metals, such as gold, with transition elements, such as iron, have unique properties and a number of potential applications, ranging from nanomedicine to magneto-plasmonics and plasmon-enhanced catalysis. Here, we investigate the localized surface plasmon resonance at the level of the single Au-Fe nanoparticle by applying a strategy that combines experimental measurements using near field electron energy loss spectroscopy with theoretical studies via a full wave numerical analysis and density functional theory calculations of electronic structure. We show that, as the iron fraction increases, the plasmon resonance is blue-shifted and significantly damped, as a consequence of the changes in the electronic band structure of the alloy. This allows the identification of three relevant phenomena to be considered in the design and realization of any plasmonic nanoalloy, specifically: the appearance of new states around the Fermi level; the change in the free electron density of the metal; and the blue shift of interband transitions. Overall, this study provides new opportunities for the control of the optical response in Au-Fe and other plasmonic nanoalloys, which are useful for the realization of magneto-plasmonic devices for molecular sensing, thermo-plasmonics, bioimaging, photocatalysis, and the amplification of spectroscopic signals by local field enhancement.