The magnetic signals of magnetite nanoparticles (NPs) preserved in rocks, soils, and sediments are effective index for paleoenvironmental reconstruction. It has been demonstrated that magnetite NPs can serve as a terminal electron sink for the microbial respiration (i.e., microbial iron reduction). The magnetic properties of magnetite NPs may be altered by microbial iron reduction, which is a critical but often overlooked process in paleomagnetism. In this study, three magnetite NPs with different particle sizes were reduced by a dissimilatory iron-reducing bacterium (Shewanella oneidensis MR-1) under a non-growth condition mimicking that of the early Earth and modern oligotrophic environment. The changes in magnetic, chemical as well as crystallographic properties of the magnetite NPs during the microbial reduction process were examined. Our results showed that the bioreduction rate of magnetite NPs was mainly controlled by their particle size and redox state. In addition, the microbial iron reduction could affect both the crystallographic and magnetic properties of three types of magnetite NPs used herein. After bioreduction, the crystal lattice parameters and magnetic susceptibility of the magnetite NPs increased, while their remanence recording capability and coercivity decreased (i.e., “softer” magnetism). Furthermore, bioreduced magnetite NPs had a larger remanence loss near the Verwey transition region with low-temperature magnetic analysis. These results indicate that the microbial reduction of magnetite NPs deserves attention when sedimentary magnetites are used in paleoenvironment reconstruction.