The effects of the cyclic prestrain on the fatigue behavior in type 304 austenitic stainless steel were investigated. Rotating bending fatigue tests have been performed in laboratory air using the specimens subjected to ±5% cyclic prestrain at room temperature (R.T.) and -5°C. Martensitic phase volume fraction of the prestrained specimen at -5°C was 48% and larger than 3.8% at R.T. The prestrained specimens exhibited higher fatigue strengths than the as-received ones, and larger volume fraction of martensitic phase resulted in the higher fatigue limit. EBSD analysis revealed that the martensitic phases were more uniformly distributed in the austenitic matrix in the cyclically-prestrained specimens than in the monotonically-prestrained ones. Fatigue crack initiation from inclusion was observed only in the cyclically-prestrained specimens at -5°C. High volume fraction and uniform distribution of martensitic phase induced the transition of crack initiation mechanism and led to the higher fatigue limit. In type 304 stainless steel with high volume fraction of strain-induced martensitic phase, the prediction of fatigue limit based on Vickers hardness could give unconservative results.