Grain size dependency of the fatigue strength was investigated using Type 316 stainless steel. The main interest of this study was to clarify the root cause of the ultimate strength dependency of fatigue strength, particularly in the high-cycle fatigue regime. Four kinds of heat treatment were applied to obtain different grain sizes. The increase in the grain size caused smaller ultimate strength. The strain-controlled fatigue test and the crack growth test were conducted at room temperature. It was shown that the materials of larger grain size tended to have a shorter fatigue life, although the grain size had little influence on the crack growth rate. The reduced fatigue life due to large grain size was deduced to have been brought about by an increase in initial crack size after an incubation period before crack initiation. It was concluded that the grain size was not the dominant factor which caused the ultimate strength dependency of the fatigue strength, although the grain size surely affected both the fatigue strength and the ultimate strength.