Nanostructured permanent magnets are gaining increasing interest and importance for applications such as generators and motors. Thermal management is a key concern since performance of permanent magnets decreases with temperature. We investigated the magnetic and thermal transport properties of rare-earth free nanostructured SrFe12O19 magnets produced by the current activated pressure assisted densification. The synthesized magnets have aligned grains such that their magnetic easy axis is perpendicular to their largest surface area to maximize their magnetic performance. The SrFe12O19 magnets have fine grain sizes in the cross-plane direction and substantially larger grain sizes in the in-plane direction. It was found that this microstructure results in approximately a factor of two higher thermal conductivity in the in-plane direction, providing an opportunity for effective cooling. The phonons are the dominant heat carriers in this type of permanent magnets near room temperature. Temperature and direction dependent thermal conductivity measurements indicate that both Umklapp and grain boundary scattering are important in the in-plane direction, where the characteristic grain size is relatively large, while grain boundary scattering dominates the cross-plane thermal transport. The investigated nano/microstructural design strategy should translate well to other material systems and thus have important implications for thermal management of nanostructured permanent magnets.