Three austenitic stainless steels – 304L, 316L and 904L - were investigated with respect to their VHCF behavior. The chemical compositions of the materials differ primarily with regard to the nickel content which influences the stability of the austenitic phase. The metastable type (304L) with its reduced Ni content (8%) has a lower stacking fault energy which promotes the formation of the deformation-induced alpha' martensite phase at slip-band intersections during static or cyclic loading. For an initially fully austenitic microstructure the phase transformation has a global effect on the fatigue behavior in the VHCF regime. It reduces the plastic strain amplitude in case of a stress controlled fatigue test. Moreover, compressive stresses are induced in surface grains due to the volume expansion during phase transformation. In combination, these two effects result in a true fatigue limit. However, for an initial microstructure consisting of austenite and more than 30% martensite, the material shows a VHCF behavior which is typical for high-strength steels with fish-eye formation and internal crack initiation even beyond 10 Mio. cycles. Although the cyclic strength increases significantly with increasing martensite volume fraction, the higher notch sensitivity of the martensitic phase is the reason why samples fail even in the VHCF range. Systematic tests were carried out with flat and pre-notched samples containing different amounts of deformation induced martensite. The results show a strong increase of the notch sensitivity at 30-Vol% alpha’-martensite, while higher martensite contents do not lead to any further significant increase of the fatigue strength. In case of the more stable type 316L with 13% Ni, no measurable amounts of martensite formation during cyclic loading in the VHCF regime could be detected by means of magnetic measurements. Localized plastic shear and slip band topography could be determined by means of serial sectioning using FIB-technique, revealing the formation of pronounced intrusions. TEM and EBSD investigations of run-out samples (109 cycles) showed that microcracks are initiated from these inclusions but the formation of failure-relevant cracks is prevented by very small martensitic domains. Hence, it is assumed that martensite formed during cyclic loading although it is not quantitatively measurable has a decisive effect on the overall VHCF behavior of 316L. The very stable type 904L with 25% Ni shows microcrack initiation at twin-boundaries and fatigue crack propagation in the VHCF regime without the influence of any phase transformation during cyclic loading. Hence, no true durability could be detected for 904L.