Temporal embeddings play a crucial role in dynamic graph neural networks (DGNNs) by capturing the temporal dynamics of interactions. However, existing Random Fourier Feature (RFF)-based methods in DGNNs directly sample Fourier frequencies from a fixed, data-independent distribution, neglecting the temporal characteristics of dynamic graphs and thereby limiting representational capacity. We propose DeepSTE, a deep spectral temporal embedding framework for dynamic graphs. DeepSTE learns RFF representations via Monte Carlo importance sampling with a tractable proposal distribution (e.g., Gaussian) to approximate the feature map of a shift-invariant or positive-definite kernel whose latent spectral density is analytically intractable. DeepSTE adopts a data-dependent scale parameter, estimated from interaction intervals, to construct the frequency proposal distribution reflecting time–frequency uncertainty. The frequency DNN and the importance-weighting DNN, initialized from the proposal distribution, are jointly optimized to model the importance-sampled spectral representation and learn adaptive temporal features. Experiments demonstrate the effectiveness of DeepSTE on dynamic link prediction and node classification tasks, while also revealing insights such as temporal embedding decay and accelerated convergence.