This paper explains a novel methodology to determine the High Cycle Fatigue (HCF) reliability of materials with defects. A defect was represented by a semi-spherical void situated at a specimen surface subjected to periodic loading. Then, the Finite Element (FE) method was carried out to find out the stress distribution near the defects for diverse sizes and diverse loadings. The Crossland stress change is studied and interpolated by a mathematical function depending on fatigue limits, defect radius, and profundity from the defect tip. The HCF strength of defect material is computed by the “stress strength” approach via the Monte Carlo sampling. This approach leads to determine Kitagawa–Takahashi diagrams, for a definite reliability, of materials with defects. The calculated HCF reliabilities agree well with fatigue tests. Obtaining Kitagawa–Takahashi diagrams with reliability level permits the engineer to be engaged in an endurance problem to compute the defective fatigue lives in safe and efficient process. As a final point, we discuss the sensitivity effects of defect size, defect free fatigue limits, affected depth, and load amplitude to envisage the fatigue reliability of materials with defects.