This investigation addresses the evolution of the microscopic and mesoscopic structures distribution, and micro-defects of carbon black (CB) filled natural rubber (NR) under uniaxial tensile condition during the fatigue process. NR was filled with three different grades CB respectively, in order to understand the impact of the structural degree and specific surface areas of CB and fatigue degree on the Payne effect. It was found that Payne effect was initially suppressed and then enhanced with increasing the degree of fatigue. The decrease of the storage modulus in the low strain area was attributed to the CB network destruction and the breakdown of the matrix cross-linking network in the early fatigue stage. However, with further increasing the degree of fatigue, the spatial rearrangement of CB aggregates with the orientation of molecular chains between adjacent CB aggregates will result in the mechanical reinforcement before the appearance of micro-defects. Moreover, it has been demonstrated that the structural degree of CB has a stronger impact on the mesoscopic structures than the specific surface area of CB during tensile fatigue process.