Attenuation of random noise is a major concern in seismic data processing. This kind of noise is usually characterized by random oscillation in seismic data over the entire time and frequency. We introduced and evaluated a low-rank and sparse decomposition-based method for seismic random noise attenuation. The proposed method, which is a trace by trace algorithm, starts by transforming the seismic signal into a new sparse subspace using the synchrosqueezing transform. Then, the sparse time-frequency representation (TFR) matrix is decomposed into two parts: (a) a low-rank component and (b) a sparse component using bilateral random projection. Although seismic data are not exactly low-rank in the sparse TFR domain, they can be assumed as being of semi-low-rank or approximately low-rank type. Hence, we can recover the denoised seismic signal by minimizing the mixed norms’ objective function by considering the intrinsically semilow-rank property of the seismic data and sparsity feature of random noise in the sparse TFR domain. The proposed method was tested on synthetic and real data. In the synthetic case, the data were contaminated by random noise. Denoising was carried out by means of the classical singular spectrum analysis (SSA) and deconvolution method for comparison. The deconvolution and the classical SSA method failed to properly reduce the noise and to recover the desired signal. We have also tested the proposed method on a prestack real data set from an oil field in the southwest of Iran. Through synthetic and real tests, the proposed method is determined to be an effective, amplitude preserving, and robust tool that gives superior results over classical SSA as conventional algorithm for denoising seismic data.