We study non-Markovianity and information flow for qubits experiencing local dephasing with an Ohmic class spectrum. We demonstrate the existence of a temperature-dependent critical value of the Ohmicity parameter s for the onset of non-Markovianity and give a physical interpretation of this phenomenon by linking it to the form of the reservoir spectrum. We demonstrate that this link holds also for more general spectra. We unveil a class of initial states for which discord is forever frozen at a positive value. We connect time invariant discord to non-Markovianity and propose a physical system in which it could be observed.