Residual life estimation occupies an important place in modern mechanical design and condition-based maintenance programs. Condition monitoring information can reflect the health status of the individual device, and the effective use of this information can help continuously predict the individual residual life. In this study, an exponential degradation model is developed to describe the degradation characteristics of devices for residual life estimation. This model is based on a gamma-prior Bayesian updating approach and an acceptance–rejection algorithm. With the gamma distribution representing the degradation rate differences among individuals, the real-world data can be described flexibly. By aid of Bayesian updating approach, the model can be updated with both the historical data and real-time monitoring signals. Furthermore, on the basis of the updated model and by means of acceptance–rejection algorithm, the residual life distribution can be computed without redundant computation. Consequently, the residual life can be estimated using the results of the residual life distribution. Finally, the proposed method is applied to real-world vibration-based degradation signals resulting from the accelerated fatigue testing of conical roller bearings. The results show that this method can avoid redundant computation and effectively estimate and update the bearing’s residual life. Therefore, the engineering value and general application of this novel method has been validated.