We derive the leading spin-dependent gravitational tail memory, which appears at the second post-Minkowskian order and behaves as u(-2) for large retarded time u. This result follows from the classical soft graviton theorem at order omega In omega as a low-frequency expansion of the gravitational waveform with frequency omega. First, we conjecture the gravitational waveform from the classical limit of the quantum soft graviton theorem up to sub-subleading order in a soft expansion, and then we derive it for a classical scattering process without any reference to the soft graviton theorem. We show that the final result of the gravitational waveform in the direct derivation completely agrees with the conjectured waveform.