Fatigue of structures or materials from repeated loading in all fields of engineering covers an enormous variety of topics, in which the very-high-cycle-fatigue (VHCF) associated with micro-scale defects or cracks induced failure is becoming the focus of attention in recent years. In this paper, the fatigue properties of a nickel-based superalloy under symmetrical and asymmetrical loads were experimentally examined at elevated temperatures in the high-cycle-fatigue (HCF) and VHCF regimes. By using the scanning electron microscope, energy dispersive X-ray spectrometer and three-dimensional imaging analysis, the micro-scale crack morphologies on the fracture surfaces were observed, and the emphasis was on studying the surface and subsurface crack nucleation and early growth behavior. Combined with the analysis of stress-life characteristics, the discussion of characteristic crack size and the evaluation of stress intensity factor at the crack tip, the failure mechanisms of nickel-based superalloy at elevated temperatures in the HCF and VHCF regimes were elucidated. Through the definition of transition crack sizes and the microstructure-scale parameters such as grain size, dislocation number, slip band width, etc., a theoretically modeling approach was proposed to predict the fatigue life of nickel-based superalloy associated with failure mechanism at elevated temperatures in the HCF and VHCF regimes.