The work aims to improve the fatigue behavior of titanium alloy, enrich the basic theory of fatigue failure of typical aviation difficult-to-cut materials and provide references for anti-fatigue manufacturing of aerospace structural parts. TC4 titanium alloy was used as the research object to conduct single factor experiments. Side milling and fatigue tests were carried out to compare the influence of machining parameters (milling linear speed vc, feed engagement fz and radial cutting depth ae) on TC4 titanium alloy specimens’ surface integrity and the influence of surface integrity indexes (mainly including surface roughness, surface microhardness and surface residual compressive stress) on fatigue behavior. From the measurement result of surface integrity, the surface roughness increased as fz and ae increased, respectively, but did not change obviously with vc. The surface microhardness increased with the increase of fz, but decreased with the increase of vc and ae, respectively. Residual compressive stress could be detected on all machined surfaces, which presented a linear decrease with the increase of vc, increased first and then decreased with the increase of ae, and had no obviously change with the variation of fz. From the fatigue performance results of specimens, microhardness had the most significant effect on the fatigue behavior of TC4 specimens. With the increase of microhardness, the fatigue behavior increases notably. Under the machining parameters of vc=20 m/min, fz=0.08 mm/z and ae=0.1 mm, TC4 specimens have the best fatigue behavior.