In order to clarify an effect of hot corrosive environment both on the fatigue strength and the fatigue fracture behavior of superalloys, the rotating-bending fatigue tests were conducted for nickel-base Inconel 751, nickel-iron-base Inconel 718 and Fe-42Ni-15Cr-3Mo alloy, at 800°C in the NazSOb-NaCl molten salt environment as well as in air. A grain size was controlled in a wide range from the viewpoint of its practical importance. It was revealed that hot corrosive environment brings about a significant fatigue strength degradation for all the alloys, in particular with reduced grain size, by affecting the initiation and propagation processes of the fatigue cracks. A grain size was confirmed to concern strongly in the corrosion fatigue crack propagation behavior. In particular, the detrimental effect of reducing a grain size was emphasized on the enhanced intergranular crack propagation. A fundamental criterion of the grain size control for the improved corrosion fatigue strength properties of superalloys was presented in connection with a Ni content.