[email protected]4 core-shell composites with tunable AlPO4 content have been successfully prepared through in situ deposition of AlPO4 on the surface of carbonyl iron. The presence of the AlPO4 layer improves the anti-oxidative ability of the internal carbonyl iron, so that surface oxidation and magnetic degradation in these composites are significantly suppressed when compared with naked carbonyl iron. It is worth noting that the AlPO4 layer can affect the electromagnetic parameters of carbonyl iron, resulting in well-matched characteristic impedance. By optimizing the AlPO4 layer content, the [email protected]4 composite can display excellent reflection loss characteristics, and qualified absorption in a very broad frequency range (2.4–18.0 GHz over −10 dB) can be achieved. The microwave absorption performance of the [email protected]4 composite is indeed superior to pure carbonyl iron as well as many previously reported carbonyl iron-based composites. More importantly, the [email protected]4 composite can maintain good microwave absorption properties after treatment at high temperature for long time periods. These results provide new insight into the fabrication of carbonyl iron-based composites with good microwave absorption and anti-oxidative properties that meet the requirements in practical applications.