We characterize the structural properties of magnetic ellipsoidal hematite colloids with an aspect ratio ρ ≈ 2.3 using a combination of small-angle X-ray scattering and computer simulations. The evolution of the phase diagram with packing fraction ϕ and the strength of an applied magnetic field B is described, and the coupling between orientational order of magnetic ellipsoids and the bulk magnetic behavior of their suspension addressed. We establish quantitative structural criteria for the different phase and arrest transitions and map distinct isotropic, polarized non-nematic, and nematic phases over an extended range in the ϕ-B coordinates. We show that upon a rotational arrest of the ellipsoids around ϕ = 0.59, the bulk magnetic behavior of their suspension switches from superparamagnetic to ordered weakly ferromagnetic. If densely packed and arrested, these magnetic particles thus provide persisting remanent magnetization of the suspension. By exploring structural and magnetic properties together, we extend the often used colloid-atom analogy to the case of magnetic spins.