In order to raise the hardness and strength of the surface layer of mechanical components and induce favourable residual compressive stresses, case-hardening procedures have become established in the heat treatment of steel. In this work, a calculation concept for the fatigue strength of components that have been case-hardened through carburizing heat-treatment is being developed. The residual stress and the load stresses in complex-shaped, carburized materials are determined using a finite element (FE) model. The fatigue limit of the components is derived using probabilistic methods and taking into account hardness gradients, residual stresses, and non-metallic inclusions. The model is validated with available axial bending fatigue test data and then used to predict the rotating bending fatigue limit of samples with various geometries and heat-treatment conditions. This work demonstrates the capability of combining probabilistic and FE-based modelling to represent complex interactions between variables that affect the fatigue of heat-treated components, such as steel cleanliness, notch shape, case-hardening depth, or loading conditions.