There is an increasing demand for rechargeable batteries in high-performance energy storage systems. The current dominating Li-ion batteries are limited by price, resource availability, as well as their theoretical capacities. So that the community has started to explore alternative battery chemistries. As a promising multivalent battery type, rechargeable magnesium batteries (RMBs) have attracted increasing attention because of high safety, high volumetric energy density, and low cost thanks to abundant resource of Mg. However, the development of high-performance anodes is still hampered by formation of passivating layers on the Mg surface. Additionally, dendrites can also grow under certain conditions with pure Mg anodes, which requires further studies for reliable operation window and substitutes. Therefore, this review specifically aims to provide an overview on the often overlooked yet very important anode materials of RMBs, with the hope to inspire more attention and research efforts for the achievement of over-all better performance of future RMBs.