In this study, the conjoint effect of a broaching operation, similar to that used for machining fir-tree slots on turbine discs, and subsequent heat treatments at 550 °C and 650 °C on the fatigue performance and corresponding crack initiation behavior of forged Inconel 718 has been investigated. Four-point bending fatigue tests were conducted under load control on specimens of two groups, i.e. a polished group and a broached group, with totally six different surface conditions. Compared to the as-polished specimens, a beneficial effect of the broaching operation was found on the fatigue life due to the high compressive residual stresses on the broached surface which transfer the fatigue crack initiation from the surface into the sub-surface region. Introducing a heat treatment generally deteriorated the fatigue performance of the alloy because of the oxidation assisted crack initiation, while the reduction in fatigue life was found to be more remarkable for the broached specimens, in particular when heat treated at 650 °C, as the thermal impact also led to a great relaxation of the compressive residual stresses; the combined effect, together with the substantial anomalies created by broaching on the surface, such as cracked carbides and machining grooves, caused an increased propensity to surface cracking in fatigue and consequently a loss of the lifetime. Furthermore, it was found that the occurrence of surface recrystallization at elevated temperatures in machined Inconel 718 could lead to intergranular oxidation, creating micro-notches as preferable sites for the fatigue crack initiation.