The fretting problem occurs at two contact surfaces sustaining small relative displacement, and it reduces the fatigue lifetime dramatically. Estimating accurate fretting fatigue lifetime plays an important role in engineering applications. Due to the complicated stress state, and high-stress gradient in the contact surface, the average methods are necessary to obtain the precise lifetime, but the critical distance for the average zone is difficult to estimate. In this work, Artificial Neural Network (ANN) tool combined with damage parameters is proposed to determine the optimal critical distance for different fretting conditions. This tool can also be used to accurately predict the crack initiation lifetime. The fretting fatigue lifetimes calculated by using this approach have shown good agreement with experimental results from literatures. In addition, rough estimates of critical distance for different cases are made based on the numerical results.