Nanocrystalline materials tend to have an inferior fatigue crack-growth behavior, compared to coarser-grained counterparts, due to the loss of crack-closure effects. Strategies to mitigate this effect are widely unknown as grain-refinement changes the strength, however, often also the fracture-mode and cyclic material behavior so that the effect of individual parameters is difficult to discriminate. To address this issue, the fatigue crack-growth behavior of a nanocrystalline austenitic-steel (316L) in two conditions with different strength but comparable grain-size is investigated. The increased strength level, realized by an annealing treatment, leads to an improvement of the fatigue crack-growth behavior.