Extracting fault frequencies from noisy vibration signal is a challenging task for bearing fault diagnosis. The state-of-the-art sparse representation (SR)-based methods usually consist of two steps: 1) fault impulse recovery in the time domain and 2) frequency transformation of the estimated signal envelope. However, any inaccurate time-domain signal recovery can cause an error accumulation problem for the following frequency transformation, and the frequency transformation itself encounters a low-resolution shortcoming especially for short-time sampling data. To handle these shortcomings, in this article, we propose a novel sparse Bayesian learning (SBL) framework to evade the time-domain signal recovery and extract the fault frequencies directly from the frequency domain. We first present a new formulation for the sparse frequency recovery problem using the sparsity structure of the envelope spectrum, and then introduce a truncated off-grid model into the SBL framework to speed up the proposed method. Moreover, an improved grid refinement is developed to jointly combat the off-grid frequency mismatch and exploit the arithmetic sparsity structure of fault frequencies. Both the simulation and experimental results indicate the effectiveness of our proposed method.