Spatio-temporal trajectory density data is used widely in, e.g., urban analytics, mobility, and epidemiology. While differential privacy guarantees are important enablers of the release and use of such data, it is challenging to offer privacy guarantees for high-resolution density data. Specifically, existing approaches inject noise into the spatial domain, failing to preserve inherent spatio-temporal correlations and suffering from severely reduced utility at fine granularities. We propose PrivSTD, a novel framework for differentially private release of spatio-temporal trajectory density data. PrivSTD leverages the Discrete Cosine Transform to project density data into the frequency domain, where spatial correlations and temporal smoothness are naturally captured by low-frequency components. To suppress noise-dominated frequencies, a Benjamini–Hochberg FDR–based adaptive truncation mechanism is introduced that preserves statistically significant structures without additional privacy cost. Furthermore, PrivSTD employs a control variate–enhanced Recorrupted-to-Recorrupted denoising model to reconstruct highquality density data without access to clean ground truth data. An experimental study shows that PrivSTD is capable outperforming existing methods, achieving 1.12X–53.89X (6.12X on average) lower error across all datasets condisidered.