This paper shows that single-domain or pseudo-single-domain (SD/PSD) magnetite grains can exist in the upper 30--45 km of the Martian crust. The upper ~50 km of the Martian crust have likely formed by volcanic eruptions on a stagnant lithosphere. A given lava flow cools very rapidly at the surface but is then gradually heated up through burial heating as it is overlain by other successive flows. The thermal evolution models of a lava flow show that its temperature remains below the magnetic blocking temperatures of magnetite, 480--580¿C, until it reaches ~30--45 km depth. The highly magnetic SD/PSD magnetite grains can easily explain the strong magnetic anomalies of Mars; less than 1% by volume of magnetite particles is sufficient.