To accurately extract fault information from rolling bearing (RB) vibration signals with strong nonlinear and non-stationary characteristics, a novel method using adaptive variational mode decomposition with noise suppression and fast spectral correlation (AVMDNS-FSC) is proposed. The AVMDNS algorithm can adaptively select VMD parameters K and α, which reduces the error caused by the improper selection of VMD parameters based on experience or prior knowledge of the signal. Meanwhile, the AVMDNS also effectively suppresses noise in intrinsic mode function (IMFs) and avoids unexpected removal of the IMFs containing important fault information. In addition, the FSC can further suppress residual noise and interference harmonics to enhance the periodic fault pulses and hence accurately extract bearing fault features. Simulation analysis and experimental studies are carried out through comparison with other methods. Results show that the AVMDNS-FSC method has higher sensitivity and effectiveness in extracting early periodic fault pulses of RB vibration signals.