Fatigue life predictions associated with the S-N curve have been largely based on empiricism or unfounded theories, or both, due to the complexity involving multiple variables such as fatigue life, applied stress, number of loading cycles, and stress ratio. A damage model proposed by Palmgren in 1924 and popularized by Miner in 1945 may be one of the most important milestones in the fatigue damage research history. Its validity and principle adopted, however, have been problematic, and many researchers have attempted refining the model without much success. The ultimate objectives of the current work are to provide a theory for mathematical validity framework of fatigue damage associated with the S-N curve and to derive a damage function capable of predicting the fatigue life. The validity framework is designed as the fundamental basis to ensure the validity of a damage function in the development process. In this paper, a theory for validity framework, consisting of axioms, relative conditions for compatibility, and boundary conditions, is developed for fatigue damage on the S-N plane at a stress ratio of zero. Also, compatibility conditions based on the new concept for fatigue damage are developed. Manifestation points for accumulated damage are defined and conceptualized for boundary conditions by differentiating between damage accumulated before failure and failure caused by damage. A selected equation for damage at failure as the reference damage is theoretically validated for further validation of damage on the S-N plane. Subsequently, a damage function capable of predicting fatigue damage is proposed following the validation process. Comparisons between experimental results from two stress level sequence loading and theoretical fatigue life predictions are made and a close agreement between them was found. With the benefits of the new compatibility conditions and criteria we developed, an evaluative review on the fatigue damage models is presented.