An extensive review of probabilistic techniques in fatigue analysis indicates that there is a need for new microstructure-sensitive methods in describing the effects of notches on the fatigue life reduction in cyclically loaded components. Of special interest are notched components made from polycrystalline nickel-base superalloys, which are used for high temperature applications in aircraft gas turbine engine disks. Microstructure-sensitive computational crystal plasticity is combined with novel probabilistic techniques to determine the probability of failure of notched components based on the distribution of slip within the notch root region and small crack initiation processes. The key microstructure features of two Ni-base superalloys, a fine and coarse grain IN100, are reviewed and the method in which these alloys are computationally modeled is presented. Next, the geometric model of the notched specimens and method of finite element polycrystalline reconstruction is demonstrated. Shear-based fatigue indicator parameters are used to characterize the shear-based, mode I formation and propagation of fatigue cracks. Finally, two different probabilistic approaches are described in this work including a grain-scale approach, which describes the probability of forming a crack on the order of grain size, and a transition crack length approach, which describes the probability of forming and propagating a crack to the transition crack length. These approaches are used to construct cumulative distribution functions for the probability of failure as a function of various notch root sizes and strain load amplitudes.