Nickel based super-alloys when exposed to a combination of high temperature and low melting point fused corrosion products, result in early fatigue failure compared to their response in high temperature benign environment. The high cycle fatigue (HCF) (at 550 and 625°C) as well as fatigue crack growth (at 550°C) behavior of a nickel based super alloy 718 in hot corrosive environment (Na2SO4+NaCl salt coating), typical of marine engine environment, is presented in this paper. At least an order of magnitude decrease in fatigue life is noticed when the temperature is changed from 550 to 625°C at stress levels below 450 MPa. The statistical analysis of scatter in fatigue lives at different stress levels is performed and a Weibull–Inverse power law model is fitted to the stress–fatigue life data of alloy 718 in hot corrosive environment. Fracture surface examination of hot corrosion fatigue failures showed higher crack growth rates compared to uncoated high temperature HCF fracture surfaces. Fatigue crack growth rate at 550°C in a hot corrosive environment increases by an order of magnitude at 0.5 Hz in the Paris region compared to crack growth kinetics at 2 Hz in lab air environment at the same temperature. The fracture surface shows a mix of transgranular and intergranular mode of crack in the propagation region at 0.5 Hz. A fatigue failure diagram is proposed combining the thresholds of maximum stress level from endurance tests and maximum stress intensity factor from fatigue crack growth tests to demarcate the regions of propagating and non-propagating cracks during hot corrosion fatigue. The complexities in incorporating the effect of loading frequency in fatigue failure diagram are highlighted.