We report on a new mechanism for heat conduction in the neutron star crust. We find that collective modes of superfluid neutron matter, called superfluid phonons, can influence heat conduction in magnetized neutron stars. They can dominate the heat conduction transverse to the magnetic field when the magnetic field B ≥ 10¹³G. At a density of ρ ~ 10¹²-10¹⁴g/cm³, the conductivity due to superfluid phonons is significantly larger than that due to lattice phonons and is comparable to electron conductivity when the temperature ~10⁸K. This new mode of heat conduction can limit the surface anisotropy in highly magnetized neutron stars. Cooling curves of magnetized neutron stars with and without superfluid heat conduction could show observationally discernible differences.