The fatigue performance of high strength aluminum alloys used in planes, trains, trucks and automobiles is notoriously poor. Engineers must design around this important limitation to use Al alloys for light-weighting of transportation structures. An alternative concept for microstructure design for improved fatigue strength is demonstrated in this work. Microstructures are designed to exploit the mechanical energy imparted during the initial cycles of fatigue to dynamically heal the inherent weak points in the microstructure. The fatigue life of the highest strength Aluminum alloys is improved by 25x, and the fatigue strength is raised to ~1/2 the tensile strength. The approach embraces the difference between static and dynamic loading and represents a conceptual change in microstructural design for fatigue.