Meteorites contain a record of their thermal and magnetic history, written in the intergrowths of iron-rich and nickel-rich phases that formed during slow cooling. Of intense interest from a magnetic perspective is the "cloudy zone," a nanoscale intergrowth containing tetrataenite-a naturally occurring hard ferromagnetic mineral that has potential applications as a sustainable alternative to rare-earth permanent magnets. Here we use a combination of high-resolution electron diffraction, electron tomography, atom probe tomography (APT), and micromagnetic simulations to reveal the 3D architecture of the cloudy zone with subnanometer spatial resolution and model the mechanism of remanence acquisition during slow cooling on the meteorite parent body. Isolated islands of tetrataenite are embedded in a matrix of an ordered superstructure. The islands are arranged in clusters of three crystallographic variants, which control how magnetic information is encoded into the nanostructure. The cloudy zone acquires paleomagnetic remanence via a sequence of magnetic domain state transformations (vortex to two domain to single domain), driven by Fe-Ni ordering at 320 °C. Rather than remanence being recorded at different times at different positions throughout the cloudy zone, each subregion of the cloudy zone records a coherent snapshot of the magnetic field that was present at 320 °C. Only the coarse and intermediate regions of the cloudy zone are found to be suitable for paleomagnetic applications. The fine regions, on the other hand, have properties similar to those of rare-earth permanent magnets, providing potential routes to synthetic tetrataenite-based magnetic materials.