Overall damage tolerances of the heat-treated 34CrMo4 steels having ferritic-pearlitic, bainitic, and tempered-martensitic microstructures were evaluated based on their threshold stress intensity factor prior to small crack propagation, fatigue strength, and fracture toughness under static loading. Kitagawa-Takahashi diagrams were constructed to determine the limiting size of small crack propagation. The micromechanical effects of carbide morphology and phase distribution on quasi-static and dynamic mechanical properties were also elaborated. Fractographic investigations were carried out on the notched fatigue test specimens to distinguish deterioration and deformation mechanism of the microstructure under reversed cyclic loads. Finally, improvements in the damage tolerance were discussed to present the advantages and disadvantages of each heat treatment procedure to minimize in-service fatigue failures.