Time-varying fault impulse amplitude and time-varying fault impulse interval are the main challenges for rolling bearing fault diagnosis under variable speed conditions. In this paper, a vibration-based rolling bearing fault characteristic frequency (FCF) estimation and novel diagnosis method under time-varying rotational speeds are proposed, using the demodulation transform. First, the FCFs with weak amplitudes are estimated, using the optimization-based demodulation transform, whose main concept is that with the optimal demodulation operator (DO), the time-varying frequency component can be transformed into a constant one and the largest peak can be detected in the spectrum of the demodulated signal. Second, the rolling bearing is successfully diagnosed with hypothesis-based demodulation transform, whose main concept is that the rotational frequency (RF)-related DOs under different fault types are estimated, based on the estimated FCFs and the fault characteristic coefficients (FCCs). Then the RF-related peak in the spectrum of the demodulated signal can be used to detect rolling bearing fault. The effectiveness of the proposed method is verified, using both simulated signal and measured vibration signal. Novel comparisons with the current methods demonstrate much better ability of the proposed method for diagnosis of rolling bearing under variable speed conditions.