Mantle xenoliths provide our clearest look at the magnetic mineral assemblages below the Earth's crust. Previous investigations of mantle xenoliths suggested the absence of magnetite and metals, and proposed that even if such minerals were present, they would be above their Curie temperatures at mantle conditions. Here we use magnetic measurements to examine four exceptionally fresh suites of xenoliths, and show that magnetite occurs systematically, albeit in variable amounts depending on the tectonic setting. Specimens from low geotherm regions hold the largest magnetic remanence. Petrographic evidence shows that this magnetite did not form through serpentinization or other alteration processes. Magnetite, which is generally stable at the P-T-fO2 conditions in the uppermost mantle, had to have formed either in the mantle or, less likely, in the volcanic conduit. In some cases, the source of the xenoliths was at temperatures <600°C, which may have allowed this portion of the lithospheric mantle to carry a magnetic remanence. Whether such magnetite carries a remanent magnetization or is simply the source of a strong induced magnetization, these new results suggest that the concept of the Moho as a major magnetic boundary needs to be revisited.