Fretting-fatigue behavior and damage accumulation under a variable-amplitude cycling load is investigated in a configuration involving a cylindrical indenter in contact with finite width plate. Relative magnitudes of cyclic tangential and bulk loads not only affect the contact conditions, but also their relative positions with respect to each other. Several stick-slip conditions on the contact surface may develop during the application of variable-amplitude fatigue load, and these are secondary and tertiary slips as well as shake-down. Further, residual shear traction develops during the application of cyclic load. The appropriate characterization of fretting-fatigue behavior or life should, therefore, include the complete history of applied cyclic tangential and bulk loads. Furthermore, experiments from a previous study conducted under a variable-amplitude fatigue loading condition are analyzed to characterize the damage accrual from its individual components involving constant-amplitude fatigue load by incorporating the contact mechanics and a multi-axial fatigue critical plane parameter. This analysis shows that there is nonlinear damage accumulation during variable-amplitude fretting-fatigue load.